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

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

long long N;
int Nodes, MyId;

void work() {
	//Within a fixed interval calculates:
	// - total - sum of all numbers
	// - lowPref - lowest sum of any prefix
	// - lowSuf - lowest sum of any sufix
	// - least - lowest sum of any substring
	
	long long intervalLen = N/Nodes;
	long long start = MyId*intervalLen;
	long long end = (MyId == Nodes-1 ? N-1 : (MyId+1)*intervalLen-1);
	
// 	fprintf(stderr, "MyId = %d  ;  start = %lld  ;  end = %lld  ;  intervalLen = %lld\n", MyId, start, end, intervalLen);
	
	long long lowPref=0, highPref=0, cur=0, lowest=0;
	
	for (long long i=start; i<=end; ++i) {
		cur += GetTaste(i);
		
		lowPref = min(lowPref, cur);
		highPref = max(highPref, cur);
		lowest = min(lowest, cur-highPref);
	}
	
	long long total = cur;
	long long lowSuf = total - highPref;
	
	//Send answer:
	PutLL(0, total);
	PutLL(0, lowPref);
	PutLL(0, lowSuf);
	PutLL(0, lowest);
	Send(0);
}

void gather() {
	//Gathers data from all instances and calculates the final answer
	
	long long total=0, lowest=0, curLowest=0;
	vector<long long> totals, lowPrefs, lowSufs;
	
	for (int i=0; i<Nodes; ++i) {
		Receive(i);
		totals.push_back(GetLL(i));
		lowPrefs.push_back(GetLL(i));
		lowSufs.push_back(GetLL(i));
		lowest = min(lowest, GetLL(i));
	}
	
	for (int i=0; i<Nodes; ++i) {
		total += totals[i];
		
		lowest = min(lowest, curLowest + lowPrefs[i]);
		curLowest = min(curLowest + totals[i], lowSufs[i]);
	}
	
	printf("%lld\n", total - lowest);
}

int main() {
	N = GetN();
	Nodes = NumberOfNodes();
	MyId = MyNodeId();
	
	work();
	
	if (MyId == 0)
		gather();
	
	return 0;
}