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 <bits/stdc++.h>
using namespace std;

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

typedef long long ll;

//vector<int> tastes;

ll sums[101];
ll results[101];
ll lresults[101];
ll rresults[101];

ll aggprefsum[101];
ll aggsufsum[101];

int main(){
	
	int nodes = NumberOfNodes();
	int inode = MyNodeId();
	
	int n = GetN();
	
	int smalln = (n+nodes-1) / nodes;
	int datafrom = smalln*inode;
	
	smalln = min(smalln, n - datafrom);
	smalln = max(smalln, 0);
	
	//tastes.resize(smalln+10);
	
	//for(int i=0; i<smalln; ++i){
	//	tastes[i] = GetTaste(datafrom + i);
	//}
	
	ll sufsummax = 0;
	ll sufsum = 0;
	for(int i=smalln-1; i>=0; --i){
		sufsum += GetTaste(datafrom + i); //tastes[i];
		sufsummax = max(sufsummax, sufsum);
	}
	
	ll prefsum = 0;
	ll prefsummax = 0;
	ll smallresult = 0;
	for(int i=1; i<=smalln; ++i){
		prefsum += GetTaste(datafrom + i-1); //tastes[i];
		prefsummax = max(prefsummax, prefsum);
		
		ll cand = sufsum - prefsum + prefsummax;
		smallresult = max(smallresult, cand);
	}
	
	PutLL(0,prefsum);
	PutLL(0,smallresult);
	PutLL(0,prefsummax);
	PutLL(0,sufsummax);
	Send(0);
	
	if(inode != 0) return 0;
	
	// instance 0 here
	
	// receive partial results
	for(int i=0; i<nodes; ++i){
		int ii = Receive(-1);
		sums[ii] = GetLL(ii);
		results[ii] = GetLL(ii);
		lresults[ii] = GetLL(ii);
		rresults[ii] = GetLL(ii);
	}
	
	ll totalsum = 0;
	for(int i=0; i<=nodes; ++i){
		aggprefsum[i] = totalsum;
		totalsum += sums[i];
	}
	totalsum = 0;
	for(int i=nodes-1; i>=0; --i){
		totalsum += sums[i];
		aggsufsum[i] += totalsum;
	}
	
	ll result = 0;
	for(int i=0; i<nodes; ++i){
		ll cand = totalsum - sums[i] + results[i];
		result = max(cand, result);
	}
	
	for(int i=0; i<nodes; ++i){
		for(int j=i+1; j<nodes; ++j){
			ll cand = aggprefsum[i] + aggsufsum[j+1] + lresults[i] + rresults[j];
			result = max(cand, result);
		}
	}
	
	printf("%lld\n", result);
	
	return 0;
}