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

int ID, NN, n, a, b;
LL sum, mn, res;

void sync()
{
	LL s = 0, m = 0;
	
	if (ID > 0) {
		Receive(ID-1);
		s = GetLL(ID-1); m = GetLL(ID-1);
	}
	
	if (ID+1 < NN) {
		PutLL(ID+1, sum + s); PutLL(ID+1, min(mn + s, m));
		Send(ID+1);
	}
	
	sum = s;
	mn = m;
}


int main()
{
	ID = MyNodeId();
	NN = NumberOfNodes();
	
	n = (Size() + NN - 1) / NN;
	a = min(Size()+1, ID*n+1);
	b = min(Size()+1, a+n);
	
	for (int i=a; i<b; ++i)
		mn = min(mn, sum += ElementAt(i));
	
	sync();
	
	for (int i=a; i<b; ++i) {
		mn = min(mn, sum += ElementAt(i));
		res = max(res, ElementAt(i) - mn);
	}
	
	if (ID+1 < NN) {
		PutLL(NN-1, res);
		Send(NN-1);
	} else {
		for (int i=0; i+1<NN; ++i)
			res = max(res, GetLL(Receive(-1)));
		printf("%lld\n", res);
	}
	
	return 0;
}