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

typedef long long ll;

int main(){
	ll n = Size();

	ll part_size = (n + NumberOfNodes() - 1)/NumberOfNodes();
	
	ll l = 1 + MyNodeId()*part_size;
  ll r = min(n+1,l + part_size);

	ll sum = 0;
	for(int i=l; i<r; ++i) sum += ElementAt(i);

	ll tmp = 0;
	ll pref = 0;
	for(int i=l; i<r; ++i){
		tmp += ElementAt(i);
		pref = max(pref,tmp);
	}

	tmp = 0;
	ll suf = 0;
	for(int i=r-1; i>=l; --i){
		tmp += ElementAt(i);
		suf = max(suf,tmp);
	}

	if(MyNodeId()>0){
		PutLL(0,sum);
		PutLL(0,pref);
		PutLL(0,suf);
		Send(0);
	}
	else{
		ll *A,*B,*C;

		A = new ll[NumberOfNodes() + 1];
		B = new ll[NumberOfNodes() + 1];
		C = new ll[NumberOfNodes() + 1];

		B[NumberOfNodes()] = 0;

		A[0] = sum;
		B[0] = pref;
		C[0] = suf;

	//	cout << A[0] << " " << B[0] << " " << C[0] << endl;

		for(int i=1; i<NumberOfNodes(); ++i){
			int ins = Receive(-1);

			A[ins] = GetLL(ins);
			B[ins] = GetLL(ins);
			C[ins] = GetLL(ins);
//			cout << A[ins] << " " << B[ins] << " " << C[ins] << endl;
		}

		ll res = max(0LL,A[0]+B[1]);

		sum = 0;
		for(int i=0; i<NumberOfNodes(); ++i){
			sum += A[i];
			A[i] += (sum-A[i]);
		}

		for(int i=0; i<NumberOfNodes(); ++i)
			res = max(max(res,B[i]),C[i]);

		for(int i=1; i<NumberOfNodes(); ++i)
			for(int j=i; j<NumberOfNodes(); ++j)
				res = max(res,C[i-1]+(A[j]-A[i-1])+B[j+1]);

		cout << res << endl;
	}

	return 0;
}