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 "kanapka.h"
#include "message.h"
#include <bits/stdc++.h>
using namespace std;
#define e1 first
#define e2 second
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
int n, m, k, a, b, c;
ll SumaWszystkich = 0;

int main() {
	boost;
	n = GetN();
	int inst = NumberOfNodes(), ID = MyNodeId();
	int dl = n / inst + 1;
	int x = ID * dl, y = min(n - 1, ID * dl + dl - 1);
	//input reading phase
	ll suma = 0;
	FOR(i, x, y) suma += GetTaste(i);
	PutLL(0, suma);
	Send(0);
	//odbieramy sume wszystkich liczb w zerze
	if (ID == 0) {
		FOR(i, 0, inst - 1) {
			Receive(i);
			SumaWszystkich += GetLL(i);
		}
	}
	
	//rozwiazujemy przypadek dla naszego fragmentu
	ll MAX = 0, PrefSum = 0, wynik = 0, smallest = INF;
	FOR(i, x, y) {
		ll A = GetTaste(i);
		PrefSum += A;
		smallest = min(smallest, PrefSum);
		wynik = min(wynik, PrefSum - MAX);
		MAX = max(MAX, PrefSum);
	}

	ll poprzPrefSum = 0;
	//teraz czas na przeslanie sum prefiksowych i minimow prefiksowych do kolejnych instancji
	if (ID != 0) {
		Receive(ID - 1);
		poprzPrefSum = GetLL(ID - 1);
		PrefSum += poprzPrefSum;
	}
	if (ID != inst - 1) {
		PutLL(ID + 1, PrefSum);
		Send(ID + 1);
	}

	//kazda instancja zna juz swoja sume prefiksowa, czas rozwiazac zadanie
	ll poprzMax = 0;
	if (ID != 0) {
		Receive(ID - 1);
		poprzMax = GetLL(ID - 1);
	}
	wynik = min(wynik, smallest + poprzPrefSum - poprzMax);
	MAX = max(poprzMax, poprzPrefSum + MAX);
	
	if (ID != inst - 1) {
		PutLL(ID + 1, MAX);
		Send(ID + 1);
	}

	PutLL(0, wynik);
	Send(0);
	
	if (ID == 0) {
		FOR(i, 0, inst - 1) {
			Receive(i);
			wynik = min(wynik, GetLL(i));
		}
		cout << max(0LL, SumaWszystkich - wynik);
	}
	
  return 0;
}