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

#include <algorithm>
#include <iostream>

using namespace std;

using LL = long long;

struct Data 
{
	LL total;
	LL best;
	LL prefix;
	LL sufix;

	void SendData(int node) { PutLL(node, total); PutLL(node, best); PutLL(node, prefix); PutLL(node, sufix); Send(node); };
	static Data ReceiveData(int node) { Receive(node); Data res; res.total = GetLL(node); res.best = GetLL(node); res.prefix = GetLL(node); res.sufix = GetLL(node); return res; };
};

inline Data operator+(const Data &a, const Data &b) 
{
	Data res;

	res.total = a.total + b.total;
	res.best = min(a.best, b.best);
	res.best = min(res.best, a.sufix + b.prefix);
	res.prefix = min(a.prefix, a.total + b.prefix);
	res.sufix = min(b.sufix, b.total + a.sufix);

	return res;
}

inline Data Compute(LL i) 
{
	LL taste = GetTaste(i);

	Data res;

	res.total = taste;
	res.best = min(taste, 0LL);
	res.prefix = res.best;
	res.sufix = res.best;

	return res;
}

Data Compute(LL start, LL end) 
{
	Data res = Compute(start);

	for (LL i = start + 1; i < end; ++i)
	{
		res = res + Compute(i);
	}

	return res;
}

int main() 
{
	int NNODES = NumberOfNodes();
	int NODE = MyNodeId();
	LL N = GetN();

	if (NNODES > N)
		NNODES = (int)N;

	if (NODE >= NNODES)
		return 0;

	LL start = N * NODE / NNODES;
	LL end = N * (NODE + 1) / NNODES;

	Data data = Compute(start, end);

	if (NODE != 0)
	{
		data.SendData(0);
	}
	else
	{
		for (int i = 1; i < NNODES; ++i)
		{
			data = data + Data::ReceiveData(i);
		}

		LL res = data.total - data.best;

		cout << res;
	}

	return 0;
}