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

int ninst,myid;
int size;

int main()
{
	ninst = NumberOfNodes();
	myid = MyNodeId();
	size = Size();

	int n = (size+ninst-1)/ninst;
	int beg = myid*n, end = myid*(n+1);
	if (beg>size) end = -1;
	end = min(end, size+1);

	long long sum,sbeg,send,smax,sall;
	sum = sbeg = send = smax = sall = 0;
	for (int i=beg;i<end;++i) {
		sall += ElementAt(i);
		sbeg = max(sbeg, sall);
		sum = max(0LL, sum+=ElementAt(i));
		smax = max(smax, sum);
	}
	send = sum;

	int power = 1;
	while (myid%(power*2)==0) {
		int fr = myid+power;
		power *= 2;
		if (fr>size) break;
		Receive(fr);
		long long sbe,sen,sma,sal;
		sbe=GetLL(fr); sen=GetLL(fr);
		sma=GetLL(fr); sal=GetLL(fr);
		sbeg = max(sbeg, sall+sbe);
		smax = max(max(smax, send+sbe), sen);
		send = max(send+sal, sen);
		sall = sall + sal;
	}
	if (myid!=0) {
		int to = myid-power;
		PutLL(to,sbeg); PutLL(to,send);
		PutLL(to,smax); PutLL(to,sall);
		Send(to);
	}
	else {
		cout << smax << '\n';
	}

	return 0;
}