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
#include <algorithm>
#include <cstdio>
using namespace std;

#include "maklib.h"
#include "message.h"

typedef long long LL;

struct node {
	LL pref, suf, in, sum;
	static node single(LL v) {
		LL t = max(v, 0LL);
		return node{t, t, t, v};
	}
};

node operator+(const node &a, const node &b) {
	return node{
		max(a.pref, a.sum + b.pref),
		max(b.suf, b.sum + a.suf),
		max(max(a.in, b.in), a.suf + b.pref),
		a.sum + b.sum
	};
}

int main(int argc, char *argv[]) {
	int nodes = NumberOfNodes();
	int id = MyNodeId();
	node ret = node::single(0);
	int n = Size();
	nodes = min(nodes, n);
	int block_size = (n+nodes-1)/nodes;
	int limit = min(n, block_size*(id+1));
	for(int i=block_size*id;i<limit;i++)
	{
		node t = node::single(ElementAt(i+1));
		ret = ret + t;
	}
	if(!id) {
		for(int i=1;i<nodes;i++)
		{
			Receive(i);
			LL pref = GetLL(i);
			LL suf = GetLL(i);
			LL in = GetLL(i);
			LL sum = GetLL(i);
			ret = ret + node{pref, suf, in, sum};
		}
		printf("%lld\n", ret.in);
	} else {
		PutLL(0, ret.pref);
		PutLL(0, ret.suf);
		PutLL(0, ret.in);
		PutLL(0, ret.sum);
		Send(0);
	}
	return 0;
}