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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// Krzysztof Małysa
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,n) for (int i = (a), i##__ = (n); i <= i##__; ++i)
#define REP(i,n) FOR(i,0,n-1)
#define FORD(i,a,n) for (int i = (a), i##__ = (n); i >= i##__; --i)
#define ALL(x) x.begin(), x.end()
#define EB emplace_back
#define ST first
#define ND second
#define OO(A) template<class... T> ostream& operator<<(ostream& os, const A<T...>& x) { return __o(os, ALL(x)); }
#define SZ(x) ((int)x.size())

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<PII> VPII;

template<class A, class B> ostream& operator<<(ostream&, const pair<A, B>&);
template<class I> ostream& __o(ostream&, I, I);
template<class T, size_t N> ostream& operator<<(ostream& os, const array<T, N>& x) { return __o(os, ALL(x)); }
OO(vector) OO(deque) OO(set) OO(multiset) OO(map) OO(multimap)
template<class A, class B> ostream& operator<<(ostream& os, const pair<A, B>& p) {
	return os << "(" << p.ST << ", " << p.ND << ")";
}
template<class I> ostream& __o(ostream& os, I a, I b) {
	os << "{";
	for (; a != b;)
		os << *a++, cerr << (a == b ? "" : " ");
	return os << "}";
}
template<class I> ostream& __d(ostream& os, I a, I b) {
	os << "{\n";
	for (I c = a; a != b; ++a)
		os << "  " << distance(c, a) << ": " << *a << endl;
	return os << "}";
}
template<class... T> void __e(T&&... a) {
	int t[] = {(cerr << forward<T>(a), 0)...}; (void)t;
	cerr << endl;
}

template<class A, class B> void mini(A& a, B&& b) { if (b < a) a = b; }
template<class A, class B> void maxi(A& a, B&& b) { if (b > a) a = b; }
int ceil2(int x) { return 1 << (sizeof(x) * 8 - __builtin_clz(x - 1)); }

#ifdef DEBUG
# define D(...) __VA_ARGS__
#else
# define D(...)
#endif

#define LOG(x) D(cerr << #x ": " << x)
#define LOGN(x) D(LOG(x) << endl)
#define DUMP(x) D(cerr << #x ": ", __d(cerr, ALL(x)) << endl)
#define E(...) D(__e(__VA_ARGS__))
#define endl '\n'
constexpr char nl = '\n';
// End of templates

#include "kanapka.h"
#include "message.h"

int main() {
	LL n = GetN();
	int non = NumberOfNodes();
	int pid = MyNodeId();

	int beg = n * pid / non;
	int end = n * (pid + 1) / non;
	// Consider interval [beg, end)
	LL sum = 0;
	LL best = 0, curr_best = 0, min_pref = 0, max_pref = 0; // min_suff = sum - max_pref
	FOR (i, beg, end - 1) {
		LL x = GetTaste(i);
		sum += x;
		mini(min_pref, sum);
		maxi(max_pref, sum);

		curr_best += x;
		if (curr_best > 0)
			curr_best = 0;
		mini(best, curr_best);
	}

	if (pid) {
		PutLL(0, sum);
		PutLL(0, best);
		PutLL(0, min_pref);
		PutLL(0, sum - max_pref); // min_suff
		Send(0);

	} else {
		struct X {
			LL sum, best, min_pref, min_suff;

			X(LL a, LL b, LL c, LL d) : sum(a), best(b), min_pref(c), min_suff(d) {}
		};

		auto merge = [](const X& a, const X& b) {
			return X {
				a.sum + b.sum,
				min(min(a.best, b.best), a.min_suff + b.min_pref),
				min(a.min_pref, a.sum + b.min_pref),
				min(b.min_suff, b.sum + a.min_suff),
			};
		};

		X curr {sum, best, min_pref, sum - max_pref}; // Current result
		E("0: ", curr.sum, " ", curr.best, " ", curr.min_pref, " ", curr.min_suff);
		FOR (i, 1, non - 1) {
			Receive(i);
			X x {0,0,0,0};
			x.sum = GetLL(i);
			x.best = GetLL(i);
			x.min_pref = GetLL(i);
			x.min_suff = GetLL(i);
			E(i, ": ", x.sum, " ", x.best, " ", x.min_pref, " ", x.min_suff);
			curr = merge(curr, x);
			E("curr: ", curr.sum, " ", curr.best, " ", curr.min_pref, " ", curr.min_suff);
		}

		cout << curr.sum - curr.best << nl;
	}
	return 0;
}