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
#include "kanapka.h"
#include "message.h"
#include <algorithm>
#include <iostream>
#define LL long long
#define MAX_NODES 100

using namespace std;

struct packet
{
	LL sum, left, right, left_max, right_max;
};

int main()
{
	ios::sync_with_stdio(0);
	int myNode = MyNodeId();
	int nodesCount = NumberOfNodes();
	long long n = GetN();
	long long step = n / (double)nodesCount + 0.5;
	if (step < 2)
		step = 2;
	nodesCount = n > 1000 ? n / (double)step + 0.5 : 1;
	if (myNode >= nodesCount) return 0;

	// split work
	LL from, to;
	from = myNode*step;
	to = (myNode + 1) * step;
	if (myNode == nodesCount - 1) to = n;

	// solve
	LL leftMin = 0, rightMin = 0, sumAll = 0, minPiece = 0, leftMax = 0;

	for (LL i = from; i < to; i++)
	{
		sumAll += GetTaste(i);
		if (sumAll < leftMin) leftMin = sumAll;
		if (sumAll > leftMax) leftMax = sumAll;
		if (sumAll - leftMax < minPiece) minPiece = sumAll - leftMax;
	}

	rightMin = sumAll - leftMax;

	if (myNode != 0)
	{
		PutLL(0, sumAll);
		PutLL(0, leftMin);
		PutLL(0, rightMin);
		PutLL(0, minPiece);
		Send(0);
		return 0;
	}

	LL nLeftMin, nRightMin, nSumAll, nMinPiece;
	for (int i = 1; i < nodesCount; i++)
	{
		Receive(i);
		nSumAll = GetLL(i);
		nLeftMin = GetLL(i);
		nRightMin = GetLL(i);
		nMinPiece = GetLL(i);

		minPiece = std::min(std::min(nMinPiece, minPiece), rightMin + nLeftMin);
		sumAll += nSumAll;
		rightMin = std::min(nSumAll + rightMin, nRightMin);			 
	}

	cout << sumAll - minPiece;
	return 0;
}