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
#include <cstdio>
#include "kanapka.h"
#include "message.h"
using namespace std;

#define MAXNODES 100
typedef long long slng;

struct sol {
	// maksymalna suma od lewej
	slng maxl;
	// maksymalna suma od prawej
	slng maxr;
	// suma
	slng sum;
	// rozwiazanie (nie przecinajace sie sumy od lewej i prawej)
	slng sol;
};

// zwraca rozwiazanie dla przedzialu [a, b-1]
struct sol solve(int a, int b) {
	struct sol ret;
	slng maxl, maxr, sum, sol;
	slng curl, curr;
	slng i;
	
	sum = 0;
	for (i = a; i < b; i++) {
		sum += GetTaste(i);
	}
	
	curr = sum;
	curl = 0;
	maxl = maxr = 0;
	sol = 0;
	for (i = a; i <= b; i++) {
		slng taste; 
		if (curr > maxr)
			maxr = curr;
		if (curl > maxl)
			maxl = curl;
		if (maxl + curr > sol)
			sol = maxl + curr;
		if (i != b) {
			taste = GetTaste(i);
			curr -= taste;
			curl += taste;
		}
	}
	
	ret.maxl = maxl;
	ret.maxr = maxr;
	ret.sum = sum;
	ret.sol = sol;
	return ret;
}

int main() {
	slng N = GetN();
	slng nodes = NumberOfNodes(), nodeid = MyNodeId();
	slng i;
	struct sol sol[MAXNODES];
	
	/*if (N < nodes*nodes) {
		if (nodeid == 0) {
			sol[0] = solve(0, N);
			printf("%lld\n", sol[0].sol);
		}
		return 0;
	}*/
	
	sol[nodeid] = solve((nodeid * N) / nodes, ((nodeid + 1) * N) / nodes);
	if (nodeid != 0) {
		PutLL(0, sol[nodeid].maxl);
		PutLL(0, sol[nodeid].maxr);
		PutLL(0, sol[nodeid].sum);
		PutLL(0, sol[nodeid].sol);
		Send(0);
		return 0;
	} else {
		for (i = 1; i < nodes; i++) {
			Receive(i);
			sol[i].maxl = GetLL(i);
			sol[i].maxr = GetLL(i);
			sol[i].sum = GetLL(i);
			sol[i].sol = GetLL(i);
		}
	}
	
	// kwadrat po node'ach wystarczy
	slng a, b;
	slng suml = 0;
	slng bestsol = 0;
	for (a = 0; a < nodes; a++) {
		slng sumr = 0;
		for (b = nodes-1; b >= a; b--) {
			if (a != b) {
				if (suml + sumr + sol[a].maxl + sol[b].maxr > bestsol)
					bestsol = suml + sumr + sol[a].maxl + sol[b].maxr;
			} else { // a == b
				if (suml + sumr + sol[a].sol > bestsol)
					bestsol = suml + sumr + sol[a].sol;
			}
			sumr += sol[b].sum;
		}
		suml += sol[a].sum;
	}
	
	printf("%lld\n", bestsol);
	return 0;
}