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

#include <algorithm>
#include <iostream>
using namespace std;
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOR(a,b,e)  for(int a=(b); a<=(e);++a)
#define FORD(a,b,e) for(int a=(b); a>=(e);--a)

long long T1[10000002];

void doWork(long long N, int nodes, int myId) {
	long long ToSend[4]; /// suma, prefiks, sufiks, prefikso-sufiks
	long long myStart = N*myId / nodes;
	long long myEnd = N*(myId+1) / nodes - 1;
	long long sumAll = 0;
	FOR(i, myStart, myEnd) {
		sumAll += GetTaste(i);
		T1[i-myStart+1] = max(T1[i-myStart], sumAll);
#ifdef _HOMEDEBUG
		cout << i << ": " << sumAll << " " << T1[i-myStart+1] << endl;
#endif
	}
	ToSend[0] = sumAll;
	ToSend[1] = T1[myEnd-myStart+1];
	sumAll = 0;
	long long T2 = 0;
	long long maxWyn = 0;
	FORD(i, myEnd, myStart) {
		sumAll += GetTaste(i);
		T2 = max(T2, sumAll);
		maxWyn = max(maxWyn, T2+T1[i-myStart]);
#ifdef _HOMEDEBUG
		cout << i << ": " << sumAll << " " << T2 << " " << maxWyn << endl;
#endif
	}
	ToSend[2] = T2;
	ToSend[3] = maxWyn;
	REP(i, 4) {
		PutLL(0, ToSend[i]);
#ifdef _HOMEDEBUG
		cout << "send " << ToSend[i] << endl;
#endif
	}
	Send(0);
}
void generateOutput(int nodes) {
		vector<long long> ranges(nodes);
		vector<long long> maxPref(nodes);
		vector<long long> maxSuf(nodes);
		vector<long long> maxPrefSuf(nodes);
		REP(i, nodes) {
			Receive(i);
			ranges[i] = GetLL(i);
			maxPref[i] = GetLL(i);
			maxSuf[i] = GetLL(i);
			maxPrefSuf[i] = GetLL(i);
		}
		vector<long long> T3(nodes+1, 0), sumBeg(nodes+1, 0);
		FOR(i, 0, nodes-1) {
			T3[i+1] = max(T3[i], sumBeg[i]+maxPref[i]);
			sumBeg[i+1] = sumBeg[i] + ranges[i];
#ifdef _HOMEDEBUG
			cout << i << "-3 " << T3[i+1] << " " << sumBeg[i+1] << endl;
#endif
		}
		vector<long long> T4(nodes+1, 0), sumEnd(nodes+1, 0);
		FORD(i, nodes-1, 0) {
			T4[i] = max(T4[i+1], sumEnd[i+1]+maxSuf[i]);
			sumEnd[i] = sumEnd[i+1] + ranges[i];
#ifdef _HOMEDEBUG
			cout << i << "-4 " << T4[i] << " " << sumEnd[i] << endl;
#endif
		}
#ifdef _HOMEDEBUG
		cout << "T3\tT4\tPrefSuf" << endl;
		REP(x, nodes+1)
			cout << T3[x] << "\t" << T4[x] << "\t" << maxPrefSuf[x] << endl;
#endif
		long long totalMax = 0;
#ifdef _HOMEDEBUG
		cout << "totalMax" << endl;
#endif
		REP(i, nodes) {
			long long m1 = T3[i]+T4[i],
								m2 = sumBeg[i]+sumEnd[i+1]+maxPrefSuf[i];
			totalMax = max(totalMax, max(m1, m2));
#ifdef _HOMEDEBUG
			cout << m1 << " " << m2 << " -> " << totalMax << endl;
#endif
		}
		cout << totalMax;
	}

int main() {
#if defined(_HOMEDEBUG) || defined(_HOMEDEBUG1)
	GetN();
	int instances = 100;
	REP(x, instances) {
	WORKING_THREAD(x);
		doWork(GetN(), instances, x);
	}
	WORKING_THREAD(0);
	generateOutput(instances);
#else
	int nodes = NumberOfNodes();
	int myId = MyNodeId();
	doWork(GetN(), nodes, myId);
	if(myId == 0)
		generateOutput(nodes);
#endif
  return 0;
}