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
//#include <message.h>
#include <stdio.h>
//#include "sandwich.h"
#include "message.h"
#include "kanapka.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define MASTER_NODE 0
#define DONE -1
const ll INF = 1ll << 62;
ll T[5000100];
ll S[5000100];
ll Sr[5000100];
void wyslij(int target, ll x)
{
	PutLL(target, x);
	Send(target);
}
ll odbierz(int target)
{
	Receive(target);
	return GetLL(target);
}
int main()
{
	ll N = GetN();
	//N = 998;
	ll nodes = NumberOfNodes();
	ll myid = MyNodeId();
	nodes = min(nodes, N);
	if(myid >= nodes) return 0;
	ll begin = N*myid/nodes;
	ll end = N*(myid+1)/nodes;
	end -= begin;
	//printf("beg = %lld end = %lld\n", begin, end);
	//return 0;
	for(ll i = 0; i < end; ++i)
		T[i] = GetTaste(begin+i);
	ll sum = 0;
	for(int i = 0; i < end; ++i)
	{
		sum += T[i];
		S[i] = sum;
	}
	for(int i = end-1; i >= 0; --i)
		Sr[i] = Sr[i+1] + T[i];
	ll Sleft = 0;
	ll Sright = 0;
	if(myid != 0)
		Sleft = odbierz(myid-1);
	if(myid != nodes-1)
		wyslij(myid+1, Sleft + sum);
	if(myid != nodes-1)
		Sright = odbierz(myid+1);
	if(myid != 0)
		wyslij(myid-1, Sright + sum);
	for(int i = 1; i < end; ++i)
		S[i] = max(S[i-1], S[i]);
	for(int i = end-2; i >= 0; --i)
		Sr[i] = max(Sr[i], Sr[i+1]);
	for(int i = 0; i < end; ++i)
	{
		Sr[i] += Sright;
		S[i] += Sleft;
	}
	ll maxleft = 0;
	ll maxright = 0;
	if(myid != 0)
		maxleft = odbierz(myid-1);
	if(myid != nodes-1)
		wyslij(myid+1, max(maxleft, S[end-1]));
	if(myid != nodes-1)
		maxright = odbierz(myid+1);
	if(myid != 0)
		wyslij(myid-1, max(maxright, Sr[0]));
	Sr[end] = maxright;
	int ind = end;
	while(ind > 0 && Sr[ind] > Sr[ind-1]){ Sr[ind-1] = Sr[ind]; --ind;}
	S[0] = max(S[0], maxleft);
	ind = 1;
	while(ind < end && S[ind] < S[ind-11]) {S[ind] = S[ind-1];   ++ind;}
	ll maxloc = 0;
	for(int i = 0; i < end; ++i)
		maxloc = max(maxloc, S[i] + Sr[i+1]);
	wyslij(0, maxloc);
	if(myid == 0)
	{
		for(int i = 0; i < nodes; ++i)
			maxloc = max(maxloc, odbierz(i));
		printf("%lld\n", maxloc);
	}
	
	
}