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

#include <algorithm>
#include <iostream>
#include <vector>

const int MAIN_NODE = 0;

struct result {
	long long maxsum, maxpref, maxsuf, totalsum;
	result() : maxsum(0), maxpref(0), maxsuf(0), totalsum(0) { }
};

result solve_subarray() {
	long long curpref = 0, cursum = 0, cursuf = 0;
	result res;

	int begin = static_cast<long long>(Size()) * MyNodeId() / NumberOfNodes();
	int end = static_cast<long long>(Size()) * (MyNodeId() + 1) / NumberOfNodes();

	for(int i = begin; i < end; ++i) {
		int curval = ElementAt(i + 1);

		curpref += curval;
		cursuf -= curval;
		cursum += curval;
		if(cursum < 0)
			cursum = 0;

		res.maxpref = std::max(res.maxpref, curpref);
		res.maxsum = std::max(res.maxsum, cursum);
		res.maxsuf = std::min(res.maxsuf, cursuf);
	}

	res.totalsum = curpref;
	res.maxsuf += res.totalsum;

	return res;
}

long long reduce(const std::vector<result> &data) {
	long long curres = 0, maxres = 0;

	for(const result &res : data) {
		/* Optimal segment is contained in res */
		maxres = std::max(maxres, res.maxsum);

		/* Optimal segment ends at res */
		maxres = std::max(maxres, curres + res.maxpref);
		
		/* Optimal segment contains whole res or only a suffix of it*/
		curres = std::max(curres + res.totalsum, res.maxsuf);
		maxres = std::max(maxres, curres);
	}

	return maxres;
}

void send_result(const result &res) {
	PutLL(MAIN_NODE, res.maxsum);
	PutLL(MAIN_NODE, res.maxpref);
	PutLL(MAIN_NODE, res.maxsuf);
	PutLL(MAIN_NODE, res.totalsum);
	Send(MAIN_NODE);
}

result recv_result(int source) {
	if(source == MAIN_NODE)
		return solve_subarray();
	else {
		result res;

		Receive(source);
		res.maxsum = GetLL(source);
		res.maxpref = GetLL(source);
		res.maxsuf = GetLL(source);
		res.totalsum = GetLL(source);

		return res;
	}
}

int main() {
	if(MyNodeId() != MAIN_NODE) {
		send_result(solve_subarray());
	}
	else {
		std::vector<result> results(NumberOfNodes());
		for(int i = 0; i < NumberOfNodes(); ++i)
			results[i] = recv_result(i);

		std::cout << reduce(results) << std::endl;
	}
}