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
#define NDEBUG
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
#define TRACE(x) cerr<<"# "#x<<endl;
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<endl;
typedef unsigned long long ULL;
typedef long long LL;
const int INF = 0x7FFFFFFF;

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

struct RESULT {
	LL s,l,r;
};

int main() {
	int nodes = NumberOfNodes();
	int myNodeId = MyNodeId();
	int size = Size();
	int elementsPerTask = size / nodes;

	if(elementsPerTask * nodes != size) {
		++elementsPerTask;
	}

	int start = 1 + myNodeId * elementsPerTask;
	int end = (myNodeId + 1) * elementsPerTask;

	LL best = 0ll;
	LL s = 0ll;
	LL l = 0ll;
	LL r = 0ll;
	LL b = 0ll;

	if(start <= size) {
		if(end > size) { end = size; }

		for(auto i=start; i<=end ;++i) {
			int x = ElementAt(i);

			if((s += x) > l) { l = s; }

			LL rx = r + x;
			r = (rx > 0ll) ? rx : 0ll;

			if((b += x) > 0ll) {
				if(b > best) { best = b; }
			} else {
				b = 0ll;
			}
		}
	}	

	if(0 != myNodeId) {
		PutLL(0, s);
		PutLL(0, l);
		PutLL(0, r);
		PutLL(0, best);
		Send(0);
	} else {
		RESULT all[nodes];

		for(auto i=1; i<nodes ;++i) {
			int n = Receive(-1);
			all[n].s = GetLL(n);
			all[n].l = GetLL(n);
			all[n].r = GetLL(n);
			int b = GetLL(n);
			if(b > best) { best = b; }
		}

		for(auto i=1; i<nodes ;++i) {
			b = r + all[i].l;
			if(b > best) { best = b; }
	
			r += all[i].s;

			if(all[i].r > r) { r = all[i].r; }
		}

		printf("%lld\n", best);
	}

	return 0;
}