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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include "maklib.h"
#include "message.h"

using namespace std;

typedef long long LL;


int nodeCount, nodeNum, tabN, tabLeft, tabRight;

void get_info(){
	nodeCount = NumberOfNodes();
	nodeNum = MyNodeId();
	tabN = Size();
	
	int siz;
	
	if(nodeNum != nodeCount-1)
		siz = tabN / nodeCount;
	else
		siz = tabN - (tabN/nodeCount)*(nodeCount-1);
	
	tabLeft = (tabN/nodeCount)*nodeNum + 1;
	tabRight = tabLeft + siz;
	
	//fprintf(stdout, "Node %d: [%d,%d)\n", nodeNum, tabLeft, tabRight);
}

LL resultLeft, resultRight, resultAll, sumAll;

void process_data(){
	LL resultAct, resLAct, resRAct;
	
	resultLeft = resultRight = resultAll = resultAct = resLAct = resRAct = sumAll = 0;
	
	// w przebiegu od lewej do prawej znajdujemy wynik
	// dla prefiksu i dla podciagu oraz sume
	for(int i = tabLeft; i < tabRight; i++){
		int elem = ElementAt(i);
	
		sumAll += elem;
	
		resLAct += elem;
		resultAct = max(resultAct+elem, 0LL);
		
		resultLeft = max(resultLeft, resLAct);
		resultAll = max(resultAll, resultAct);
	}
	
	// w przebiegu od prawej do lewej znajdujemy wynik
	// dla sufiksu
	for(int i = tabRight-1; i >= tabLeft; i--){
		int elem = ElementAt(i);
		
		resRAct += elem;
		resultRight = max(resultRight, resRAct);
	}
	
	//fprintf(stdout, "Node %d: [%d,%d); res=(%lld,%lld,%lld,%lld)\n",
	//	nodeNum, tabLeft, tabRight, resultLeft,resultRight,resultAll,sumAll);
}

vector<LL> Left, Right, All, Sum;

void fetch_results(){
	if(nodeNum != 0){
		PutLL(0, resultLeft);
		PutLL(0, resultRight);
		PutLL(0, resultAll);
		PutLL(0, sumAll);
		Send(0);
	} else {
		Left.push_back(resultLeft);
		Right.push_back(resultRight);
		All.push_back(resultAll);
		Sum.push_back(sumAll);
		
		for(int node = 1; node < nodeCount; node++){
			Receive(node);
			Left.push_back(GetLL(node));
			Right.push_back(GetLL(node));
			All.push_back(GetLL(node));
			Sum.push_back(GetLL(node));
		}
	}
}

void find_final_result(){
	if(nodeNum != 0) return;
	
	LL best = 0;
	
	// pojedyncze czesci
	for(int i = 0; i < nodeCount; i++)
		best = max(best, All[i]);
	
	// teraz przedzialy
	LL res = 0;
	for(int L = 0; L < nodeCount; L++){
		res = Right[L];
		for(int R = L+1; R < nodeCount; R++){
			best = max(best, res+Left[R]);
			res += Sum[R];
		}
	}
	
	printf("%lld\n", best);
}


int main(){
	get_info();
	process_data();
	fetch_results();
	find_final_result();
}