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
96
97
98
#include "message.h"
#include "kanapka.h"

#include <iostream>
#include <cstdio>

const int MAXN = 5 * 10000 * 10000;

int main() {
	int instancesCount = NumberOfNodes();
	int id = MyNodeId();
	long long sandwichLen = GetN();

	long long intervalBegin = id * (sandwichLen / instancesCount + 1);
	long long intervalEnd = std::min((id + 1) * (sandwichLen / instancesCount + 1) - 1, sandwichLen - 1);
	int realInstancesCount = (sandwichLen / (sandwichLen / instancesCount + 1)) + (sandwichLen % (sandwichLen / instancesCount + 1) != 0);
	if (intervalBegin >= sandwichLen) {
		return 0;
	}

	long long currentPref = 0, prefBefore = 0, currentSuf = 0, sufBefore = 0;
	long long int minPref = 0, sum = 0, minSuf = 0, minSum = 0, maxPref = 0;
	for (long long i = 0; i <= intervalEnd - intervalBegin; i++) {
		currentPref = prefBefore + GetTaste(intervalBegin + i);
		prefBefore = currentPref;

		sum += GetTaste(intervalBegin + i);
		minPref = std::min(minPref, currentPref);
		minSum = std::min(minSum, currentPref - maxPref);
		maxPref = std::max(maxPref, currentPref);
	}

	for (int i = 0; i <= intervalEnd - intervalBegin; i++) {
		currentSuf = sufBefore + GetTaste(intervalBegin + i);
		sufBefore = currentSuf;
	}

	if (id == 0) {
		long long *prefixesTab = new long long[instancesCount + 2];
		long long *sufixesTab = new long long[instancesCount + 2];
		long long *sumsTab = new long long[instancesCount + 2];
		long long *sumsPrefixes = new long long[instancesCount + 2];
		long long result = 0;
		long long totalSum = 0;

		prefixesTab[0] = minPref;
		sufixesTab[0] = minSuf;
		sumsTab[0] = sum;
		totalSum += sum;
		result = std::min(result, minSum);
		for (int i = 1; i < realInstancesCount; i++) {
			long long recId = Receive(-1);
			long long gotPref = GetLL(recId);
			long long gotSuf = GetLL(recId);
			long long gotSum = GetLL(recId);
			long long gotMinSum = GetLL(recId);

			prefixesTab[recId] = gotPref;
			sufixesTab[recId] = gotSuf;
			sumsTab[recId] = gotSum;
			totalSum += gotSum;
			result = std::min(result, gotMinSum);
		}

		for (int i = 0; i < realInstancesCount; i++) {
			if (i > 0) {
				sumsPrefixes[i] = sumsPrefixes[i - 1] + sumsTab[i];
			} else {
				sumsPrefixes[i] = sumsTab[i];
			}
		}

		for (int iB = 0; iB < realInstancesCount; iB++) {
			for (int iE = iB + 1; iE < realInstancesCount; iE++) {
				long long currentMinSum = sufixesTab[iB] + prefixesTab[iE];
				currentMinSum += sumsPrefixes[iE - 1] - sumsPrefixes[iB];

				result = std::min(result, currentMinSum);
			}
		}

		printf("%lld\n", totalSum - result);

		delete[] prefixesTab;
		delete[] sufixesTab;
		delete[] sumsTab;
		delete[] sumsPrefixes;

	} else {
		PutLL(0, minPref);
		PutLL(0, minSuf);
		PutLL(0, sum);
		PutLL(0, minSum);
		Send(0);
	}

	return 0;
}