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

#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

void calculate(long long fromIdx, long long toIdx) {
	long long sum;
	long long leftMax;
	long long rightMax;
	if (toIdx - fromIdx == 1) {
		leftMax = 0;
		sum = GetTaste(fromIdx);
		rightMax = sum;
	} else {
		leftMax = 0;
		sum = 0;
		rightMax = 0;
		long long rightMaxIdx = -1;
		for (int i = fromIdx; i < toIdx; i++) {
			long long val = GetTaste(i);
			sum += val;
			long long tmpLeftSum = max(sum, 0LL);
			if (sum > leftMax || i == fromIdx) {
				if (rightMaxIdx > i) {
					leftMax = tmpLeftSum;
				} else {
					long long tmpRightSum = 0;
					long long maxTmpRightSum;
					for (long long j = toIdx - 1; j > i; j--) {
						tmpRightSum += GetTaste(j);
						maxTmpRightSum = max(tmpRightSum, 0LL);
						if (maxTmpRightSum + tmpLeftSum > rightMax + leftMax) {
							rightMax = maxTmpRightSum;
							rightMaxIdx = j;
							leftMax = tmpLeftSum;
						}
					}
				}
			}
		}
	}
	int receiver = NumberOfNodes() - 1;
	PutLL(receiver, leftMax);
	PutLL(receiver, sum);
	PutLL(receiver, rightMax);
	Send(receiver);
}

const int MIN_ELEMENTS = 20;

int main() {
	int id = MyNodeId();
	int nodes = NumberOfNodes();
	int workers = nodes;
	long long N = GetN();
	
	long long size = N / nodes;
	if (size < MIN_ELEMENTS) {
		workers = (N / MIN_ELEMENTS) + (N % MIN_ELEMENTS == 0 ? 0 : 1);
		size = (N / workers) + (N % workers == 0 ? 0 : 1);;
	}

	if (id < workers - 1) {
		calculate(id * size, id * size + size);
	} else if (id == workers - 1) {
		calculate(id * size, N);
	}

	// Last node is receiver
	if (id == nodes - 1) {
		long long lefts[workers];
		long long totals[workers];
		long long rights[workers];
		for (int i = 0; i < workers; i++) {
			int sender = Receive(-1);
			lefts[sender] = GetLL(sender);
			totals[sender] = GetLL(sender);
			rights[sender] = GetLL(sender);
		}

		if (workers == 1) {
			cout << max(0ll, max(totals[0], lefts[0] + rights[0])) << endl;
			return 0;
		}

		long long leftSum[workers + 1];
		long long leftTotalSum[workers + 1];
		long long rightSum[workers + 2];
		long long rightTotalSum[workers + 2];
		leftSum[0] = 0;
		leftTotalSum[0] = 0;
		rightSum[0] = 0;
		rightSum[workers + 1] = 0;
		rightTotalSum[0] = 0;
		rightTotalSum[workers + 1] = 0;

		for (long long i = 0; i < workers; i++) {
			leftSum[i + 1] = leftTotalSum[i] + lefts[i];
			leftTotalSum[i + 1] = leftTotalSum[i] + totals[i];
		}
		for (long long i = workers; i > 0; i--) {
			rightSum[i] = rightTotalSum[i + 1] + rights[i - 1];
			rightTotalSum[i] = rightTotalSum[i + 1] + totals[i - 1];
		}
		long long leftMax = 0;
		long long rightMax = 0;
		long long totalMax = rightTotalSum[1];
		for (long long i = 1; i < workers + 1; i++) {
			if (leftSum[i] > leftMax) {
				long long right = 0;
				for (long long j = i; j <= workers + 1; j++) {
					if (rightSum[j] > right) {
						right = rightSum[j];
						if (leftSum[i] + right > totalMax) {
							leftMax = leftSum[i];
							totalMax = leftMax + right;
							rightMax = right;
						}
					}
				}
			}
		}
		cout << max(0ll, max(totalMax, leftMax + rightMax)) << endl;
	}
	return 0;
}