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
#include <cstdio>
#include <algorithm>
using namespace std;

#include "maklib.h"
#include "message.h"

#define MINIMUM_ELEMS_PER_NODE 10000

class BestResult {
private:
	long long int left;
	long long int right;
	long long int total;
	long long int bestInside;

public:
	BestResult(int value) : left(value), right(value), total(value), bestInside(value) {}

	void mergeRight(const long long int value) {
		long long int l = max(left, total + value);
		long long int r = max(value, value + right);
		long long int t = total + value;
		long long int i = max(right + value, max(bestInside, value));

		left = l;
		right = r;
		total = t;
		bestInside = i;
	}

	void mergeRight(const long long l2, const long long r2, const long long t2, const long long i2) {
		long long int l = max(left, total + l2);
		long long int r = max(r2, t2 + right);
		long long int t = total + t2;
		long long int i = max(right + l2, max(bestInside, i2));

		left = l;
		right = r;
		total = t;
		bestInside = i;
	}
				
	void printResult() {
		printf("%lld\n", max(left, max(right, max(total, bestInside))));
	}

	long long int sendTotal(int address) {
		PutLL(address, left);
		PutLL(address, right);
		PutLL(address, total);
		PutLL(address, bestInside);
		Send(address);
	}
};

int main() 
{
	int size = Size();
	int numOfNodes = NumberOfNodes();
	int myNodeId = MyNodeId();

	int elemsPerNode = (size % numOfNodes) ? ((size / numOfNodes) + 1) : (size / numOfNodes);
	if (elemsPerNode < MINIMUM_ELEMS_PER_NODE) {   
		elemsPerNode = MINIMUM_ELEMS_PER_NODE;
	}

	int numOfNodesUsed = (size % elemsPerNode) ? ((size / elemsPerNode) + 1) : (size / elemsPerNode);

	if (myNodeId < numOfNodesUsed) {
		int startElemId = myNodeId * elemsPerNode;
		int endElemId = min(size, startElemId + elemsPerNode);

		BestResult localResult(ElementAt(startElemId+1));
		for (int i = startElemId+1; i < endElemId; ++i) {
			localResult.mergeRight(ElementAt(i+1));
		}

		if (myNodeId > 0) {
			localResult.sendTotal(0);
		} else {
			for (int i = 1; i < numOfNodesUsed; ++i) {
				Receive(i);
				localResult.mergeRight(GetLL(i), GetLL(i), GetLL(i), GetLL(i));
			}
			localResult.printResult();
		}
	}

	return 0;
}