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

#include <algorithm>
#include <iostream>
using namespace std;

//#define dump(...) cerr << #__VA_ARGS__ " = " << __VA_ARGS__ << endl;
#define dump(...) 

#define MAX_NODES 100

int maxPrefixes[MAX_NODES];
int maxSubs[MAX_NODES];
int maxSuffixes[MAX_NODES];
int sums[MAX_NODES];

int main()
{
	int const MinGroupSize = 1; //5;
	int const N = Size();
	int const MaxNodesCnt = NumberOfNodes();
	int const GroupSize = max(MinGroupSize, (N + MaxNodesCnt - 1) / MaxNodesCnt);
	int const UsedNodesCnt = (N + GroupSize - 1) / GroupSize;

	int const Id = MyNodeId();
	if (Id >= UsedNodesCnt)
		return 0;

	int const Start = 1 + Id * GroupSize;
	int const End = min(N, Start + GroupSize - 1);

	int maxSub = 0;
//	int curSubStart = 0;
	int curSub = 0;
	int maxPrefix = 0;
	int curPrefix = 0;
	for (int i = Start; i <= End; i++)
	{
dump(i);
		int const x = ElementAt(i);
dump(x);
		curSub = max(0, curSub + x);
dump(curSub);
		maxSub = max(maxSub, curSub);
dump(maxSub);
		curPrefix += x;
dump(curPrefix);
		maxPrefix = max(maxPrefix, curPrefix);
dump(maxPrefix);
	}

	PutInt(0, maxPrefix);
	PutInt(0, maxSub);
	PutInt(0, curSub);
	PutInt(0, curPrefix);
	Send(0);

	if (Id > 0)
		return 0;
dump(UsedNodesCnt);

	for (int i = UsedNodesCnt; i; i--)
	{
		int const Id = Receive(-1);
		maxPrefixes[Id] = GetInt(Id);
		maxSubs[Id] = GetInt(Id);
		maxSuffixes[Id] = GetInt(Id);
		sums[Id] = GetInt(Id);
	}

//	for (int i = 0; i < UsedNodesCnt; i++)
//	{
//cerr << i << " " << maxPrefixes[i] << " " << maxSubs[i] << " " << maxSuffixes[i] << " " << sums[i] << endl;
//	}

	maxSub = curSub = 0;
	for (int i = 0; i < UsedNodesCnt; i++)
	{
dump(i);
dump(maxSubs[i]);
dump(maxPrefixes[i]);
dump(maxSuffixes[i]);
dump(sums[i]);
		maxSub = max(maxSub, maxSubs[i]);
dump(maxSub);
		maxSub = max(maxSub, curSub + maxPrefixes[i]);
dump(maxSub);
		curSub = max(maxSuffixes[i], curSub + sums[i]);
dump(curSub);
		maxSub = max(maxSub, curSub);
dump(maxSub);
	}

	cout << maxSub << endl;
}