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

using namespace std;

#define T(i) (ElementAt((i)+1))

long long L[102];
long long R[102];
long long M[102];
long long S[102];
int res[102];

int main()
{
	int n = Size();
	long long pref=0,pref_ind=0,suf=0,suf_ind=0,mx=0,mx_ind=0;
	long long p = 0, q = 0, m = 0;
	int ID = MyNodeId();
	int NN = NumberOfNodes();
	long long s = 0ll;
	
	for (int i = (ID*n)/NN; i < ((ID+1)*n)/NN; i++)
	{
		if (i == (ID*n)/NN) p = T(i);
		else p += T(i);
		if (p > pref) pref = p, pref_ind = i;
		if (m > 0) m += T(i);
		else m = T(i);
		if (m > mx) mx = m, mx_ind = i;
		s += T(i);
	}
	
	for (int i = ((ID+1)*n)/NN-1; i >= (ID*n)/NN; i--)
	{
		if (i == ((ID+1)*n)/NN) q = T(i);
		else q += T(i);
		if (q > suf) suf = q, suf_ind = i;
	}
	
	if (ID > 0)
	{
		PutLL(0,s);
		PutLL(0,pref);
		PutLL(0,suf);
		PutLL(0,mx);
		Send(0);
		return 0;
	}
	for (int i = 0; i < NN; i++) M[i] = S[i] = L[i] = R[i] = -1;
	L[0] = pref, R[0]= suf;
	M[0] = mx;
	S[0] = s;
	for (int i = 1; i < NN; i++)
	{
		int node = Receive(-1);
		S[node] = GetLL(node);
		L[node] = GetLL(node);
		R[node] = GetLL(node);
		M[node] = GetLL(node);		
	}
	
	long long ans = M[0];
	for (int i = 0; i < NN; i++)
	{
		ans = max(ans,M[i]);
		long long x = R[i];
		for(int j = i+1; j < NN; j++)
		{
			ans = max(ans,x+L[j]);
			x += S[j];
		}
	}

	cout << ans << "\n";

	return 0;
}