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
#include "kanapka.h"

#include <algorithm>
#include <iostream>
#include "message.h"
using namespace std;

typedef long long ll;
#define FORQ(q,k,a,b) for(ll k=a, q; k < b; ++k)
#define FOR(k,a,b) for(ll k=a; k < b; ++k)
#define FOR_REV(k,a,b) for(ll k=b - 1; k >= a; --k)
#define TASTE(q, k) if((q = GetTaste(k)) || 1)
#define FOR_EACH(q,a,b) FORQ(q, k, a, b) TASTE(q, k)
#define FOR_EACH_REV(q,a,b) FORQ(q, k, a, b) TASTE(q, b - k + a - 1)

int main() {
   ll sum = 0;
   ll left = 0;
   ll right = 0;
   ll n = GetN();
   ll begin = (MyNodeId() * n) / NumberOfNodes();
   ll end = ((MyNodeId() + 1) * n) / NumberOfNodes();
   
   FOR_EACH(i, begin, end)  {
	   sum += i;
	   left = max(left, sum);
   }
   sum = 0;
   FOR_EACH_REV(i, begin, end) {
	   sum += i;
	   right = max(right, sum);
   }
   
   if (MyNodeId() > 0) {	   
	   PutLL(0, left);
	   PutLL(0, sum);
	   PutLL(0, right);
	   Send(0);
   }
   else {
	   ll lefts[100];
	   ll sums[100];
	   lefts[0] = left;
	   
	   FOR(i, 1, NumberOfNodes()) {
		   Receive(i);
		   lefts[i] = max(lefts[i - 1], sum + GetLL(i));
		   sums[i] = GetLL(i);
		   sum += sums[i];
	   }
	   
	   ll r = right;
	   right = 0;
	   sum = 0;
	   ll answer = lefts[NumberOfNodes() - 1];
	   FOR_REV(i, 1, NumberOfNodes()) {		   
		   answer = max(answer, max(0LL, sum + GetLL(i)) + max(0LL, lefts[i - 1]));		   
		   sum += sums[i];
	   }
	   cout << max(answer, sum + r) << endl;
   }
   return 0;
}