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
#include <algorithm>
#include <cstdio>
#include "kanapka.h"
#include "message.h"

struct group {
	long long int total;
	long long int left;
	long long int right;
	long long int both;

	group() {
		total = right = left = both = 0;
	}

	group(long long int number) {
		total = number;
		right = left = std::max(number, 0LL);
		both = 0;
	}

	group(long long int t, long long int l, long long int r, long long int b) : total(t), left(l), right(r), both(b) {};

	void merge(group& other)
	{
		long long int tn = total + other.total;
		long long int ln = std::max(left, total + other.left);
		long long int rn = std::max(right + other.total, other.right);
		long long int bn = std::max(both + other.total, std::max(total + other.both, left + other.right));

		total = tn;
		left = ln;
		right = rn;
		both = bn;
	}
};

group ProcessRange(long long int start, long long int end)
{
	group result;

	for (long long int i = start; i < end; ++i) {
		group current(GetTaste(i));
		result.merge(current);
	}

	return result;
}

int main() {
	long long int n = GetN();
	int id = MyNodeId();
	int cnt = NumberOfNodes();

	group result;

	if (n > 10 * cnt) {
		long long int rangeWidth = (n + cnt - 1) / cnt;
		result = ProcessRange(rangeWidth * id, std::min(n, rangeWidth * (id + 1)));

		if (id != 0) {
			PutLL(0, result.total);
			PutLL(0, result.left);
			PutLL(0, result.right);
			PutLL(0, result.both);
			Send(0);
		}
		else {
			for (int i = 1; i < cnt; ++i) {
				Receive(i);
				group resultI(GetLL(i), GetLL(i), GetLL(i), GetLL(i));
				result.merge(resultI);
			}
			printf("%lld\n", std::max(result.both, std::max(result.left, result.right)));
		}
	}
	else if (id == 0) {
		result = ProcessRange(0, n);
		printf("%lld\n", std::max(result.both, std::max(result.left, result.right)));
	}

	return 0;
}