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

pair<int,int> pre();
void input();

int n;
vector<int> a;

void solveMyPart()
{
	long long pref, suf, ret, tmp, sum;
	pref=suf=ret=tmp=0;
	for(int i=0;i<n;i++)
	{
		tmp+=a[i];
		pref=max(pref,tmp);
	}
	sum=tmp;
	tmp=0;
	for(int i=n-1;i>=0;i--)
	{
		tmp+=a[i];
		suf=max(suf,tmp);
	}
	tmp=0;
	for(int i=0;i<n;i++)
	{
		if(tmp>0)
			tmp+=a[i];
		else tmp=a[i];
		ret=max(ret,tmp);
	}
	//printf("NR %d: -- P: %lld S: %lld B: %lld SUM: %lld\n",MyNodeId(),pref,suf,ret,sum);
	PutLL(0,pref);
	PutLL(0,suf);
	PutLL(0,sum);
	PutLL(0,ret);
	Send(0);
}
void solveProblem()
{
	vector<long long> pref, suf, sum, ret;
	n=min(Size(),NumberOfNodes());
	pref.resize(n);
	suf.resize(n);
	sum.resize(n);
	ret.resize(n);
	for(int i=0;i<n;i++)
	{
		Receive(i);
		pref[i]=GetLL(i);
		suf[i]=GetLL(i);
		sum[i]=GetLL(i);
		ret[i]=GetLL(i);
	}
	long long res=0;
	vector<long long> P;
	P.resize(n);
	P[0]=sum[0];
	for(int i=1;i<n;i++)
		P[i]=P[i-1]+sum[i];
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
		{
			if(i==j)
				res=max(res,ret[i]);
			else if(j-i==1)
				res=max(res,suf[i]+pref[j]);
			else if(j-i>1)
				res=max(res,suf[i]+P[j-1]-P[i]+pref[j]);
		}
	printf("%lld\n",res);
}
int main()
{
	if(MyNodeId()>=Size())return 0;
	input();
	solveMyPart();
	if(MyNodeId()==0)
		solveProblem();
	return 0;
}
void input()
{
	pair<int,int> A=pre();
	int begin=A.first,end=A.second;
	a.resize(end-begin+1);
	n=end-begin+1;
	for(unsigned i=0;i<a.size();i++)
		a[i]=ElementAt(begin+i+1);
}
pair<int,int> pre()
{
	vector<int> V(min(NumberOfNodes(),Size()));
	for(auto it=V.begin();it!=V.end();it++)
		(*it)=Size()/V.size();
	for(unsigned i=0;i<Size()%V.size();i++)
		V[i]++;
	pair<int,int> w=make_pair(0,V[0]-1);
	for(unsigned i=1;i<=MyNodeId();i++)
	{
		w.first=w.second+1;
		w.second=w.first+V[i]-1;
	}
	return w;
}