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

struct Result {
	long long sum;
	long long minLeft, minRight;
	long long minInside;
};

int main() {
	int N = (int)GetN();
	int id = MyNodeId();
	int nodes = NumberOfNodes();
	int rangeSize = ceil((double)N / (double)nodes);
	int start = id * rangeSize;
	int end = min(start + rangeSize, N);
	
	long long sum = 0;
	long long tempLeftSum = 0, tempRightSum = 0;
	long long minLeft = 0, minRight = 0;
	long long minInside = 0, tempInside = 0;
	
	for(int i=start; i<end; i++){
		long long t = GetTaste(i);
		sum += t;
		tempLeftSum += t;
		
		if(tempLeftSum < minLeft)
			minLeft = tempLeftSum;
		
		if(tempInside < 0)
			tempInside += t;
		else
			tempInside = t;
		
		if(tempInside < minInside)
			minInside = tempInside;
	}
	
	for(int i=end-1; i>=start; i--){
		long long t = GetTaste(i);
		tempRightSum += t;
		
		if(tempRightSum < minRight)
			minRight = tempRightSum;
	}
	
	// -------- gather ------------
	
	if(id == 0){
		Result *results = new Result[nodes];
		long long sumAll = sum;
		
		results[0].sum = sum;
		results[0].minLeft = minLeft;
		results[0].minRight = minRight;
		results[0].minInside = minInside;
		
		for(int i=1; i<nodes; i++){
			Receive(i);
			results[i].sum = GetLL(i);
			results[i].minLeft = GetLL(i);
			results[i].minRight = GetLL(i);
			results[i].minInside = GetLL(i);
			
			sumAll += results[i].sum;
		}
		
		long long best = max(0LL, sumAll);
		
		for(int i=0; i<nodes; i++)
			for(int k=i; k<nodes; k++){
				if(k == i){
					best = max(best, sumAll - results[i].minInside);
				}else{
					long long temp = results[i].minRight + results[k].minLeft;
					
					for(int x=i+1; x<k; x++)
						temp += results[x].sum;
					
					best = max(best, sumAll - temp);
				}
			}
		
		cout << best << endl;
		
		delete [] results;
		
	}else{
		PutLL(0, sum);
		PutLL(0, minLeft);
		PutLL(0, minRight);
		PutLL(0, minInside);
		Send(0);
	}
	
	return 0;
}