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
#include "maklib.h"
#include "message.h"
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
typedef long long LL;

LL left[100], right[100], su[101];

int main() {
	LL n = Size();
	int k = NumberOfNodes();
	int ii = MyNodeId();
	int a = n * ii / k, b = n * (ii + 1) / k;
	LL s = 0, mi = 0, ma = 0, best = 0;
	FOR(i,a,b) {
		s += ElementAt(i + 1);
		mi = min(mi, s);
		ma = max(ma, s);
		best = max(best, s - mi);
	}
	PutLL(0, best);
	PutLL(0, s - mi);
	PutLL(0, s);
	PutLL(0, ma);
	Send(0);
	if (ii) return 0;
	best = 0;
	su[0] = 0;
	REP(j,k) {
		Receive(j);
		best = max(best, GetLL(j));
		left[j] = GetLL(j);
		su[j + 1] = su[j] + GetLL(j);
		right[j] = GetLL(j);
	}
	REP(j1,k) FOR(j2,j1+1,k)
		best = max(best, left[j1] + su[j2] - su[j1] + right[j2]);
	printf("%lld\n", best);
}