1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "kanapka.h"
#include "message.h"
#include <iostream>

using namespace std;

const int MAXNODES = 100;

long long min_suffix_tab[MAXNODES];
long long min_prefix_tab[MAXNODES];
long long all_sum_tab[MAXNODES];
long long min_inside_tab[MAXNODES];
long long tab[MAXNODES];

long long min_ll(long long a, long long b) {
  if (a < b) return a;
  return b;
}

int min_int(int a, int b) {
  if (a < b) return a;
  return b;
}

long long min_suffix;
long long min_prefix;
long long all_sum;
long long min_inside; 


void solve_for_node(long long start, long long end){
  min_suffix = 0LL;
  min_prefix = 0LL;
  all_sum = 0LL;
  min_inside = 0LL;

  for (long long i = start; i < end; i++) {
    long long  taste = GetTaste(i);
    all_sum += taste;
    min_suffix =  min_ll(min_suffix + taste, 0);
    min_inside =  min_ll(min_inside, min_suffix);
  }

  for (long long i = end - 1 ; i >= start; i--) {
    long long taste = GetTaste(i);
    min_prefix =  min_ll(min_prefix + taste,0);
  }

} 

long long solve_for_all(int number_of_nodes) {
  
  tab[0] = all_sum_tab[0];

  for (int i = 1; i < number_of_nodes ;i++) {
    tab[i] = tab[i-1] + all_sum_tab[i];
    //    cout << tab[i] << ' ';
  }

  long long m = 0LL;

  for (int i = 0; i < number_of_nodes ; i++) {
    m = min_ll(m, min_inside_tab[i]);
  } 

  for (int i = 0; i < number_of_nodes; i++) {
    for(int j = 0; j < number_of_nodes; j++) {
      if (i < j) {
	//	cout << "i:" <<  i << " " << "j:" << j ;
        long long sp = min_suffix_tab[i] + min_prefix_tab[j];
        if (i  < j -1) {
	  sp += tab[j-1] - tab[i];
	  // cout << "j" ;
	}
        m = min_ll(m, sp);
	//	cout<< endl;
      }
    }
  }

  // cout << m << endl;
  return tab[number_of_nodes - 1] - m;  
}


void send_message(){
  PutLL(0, min_suffix);
  PutLL(0, min_prefix);
  PutLL(0, all_sum);
  PutLL(0, min_inside);
  Send(0);
}


int main() {
  long long start, end;
 
  int  number_of_nodes = min_int(NumberOfNodes(),GetN());
  // number_of_nodes = 2;

  int  node_id = MyNodeId();
  long long  n = GetN();

  start = node_id * n /number_of_nodes; 
  end = (node_id + 1) * n / number_of_nodes ;
  
  if (node_id == number_of_nodes - 1) end = n;
  
  if  (node_id < number_of_nodes) {
    //  cout << start << " " << end << endl;
     solve_for_node(start, end);   
     send_message();
  }

  if (node_id == 0) {
    for(int i = 0; i < number_of_nodes ; i++) {
      Receive(i);
      min_suffix_tab[i] = GetLL(i);
      min_prefix_tab[i] = GetLL(i);
      all_sum_tab[i] = GetLL(i);
      min_inside_tab[i] = GetLL(i);     
      //  cout << i << " " <<  min_suffix_tab[i] << " " <<  min_prefix_tab[i]  << " " <<  all_sum_tab[i] << " " <<  min_inside_tab[i] << endl;   
    }

    cout << solve_for_all(number_of_nodes);
  }

   return 0;
}