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

int node,nodes,nSize,N;

void oneNode()
{
	int n,i=1,e;
	long long int s=0,ms=0;
	if(!MyNodeId())
	{
		for(;i<=N;++i)
		{
			e=ElementAt(i);
			s+=e;
			if(s<0)s=0;
			else if(s>ms)ms=s;
		}
		printf("%lld\n",ms); 
	}
}

void multiNode()
{
	int n,i,el,er;
	int l,r;
	long long int s=0,ms=0,msp=0,sl=0,sr=0,sp=0;
	l=node*nSize+1;
	r=l+nSize;
	if(node==nodes-1)r=N+1;
	for(i=l;i<r;++i)
	{
		el=ElementAt(i);
		er=ElementAt(r-(i-l+1));
		s+=el;
		sp+=el;
		ms+=er;
		if(sp<0)sp=0;
		else if(sp>msp)msp=sp;
		if(s>sl)sl=s;
		if(ms>sr)sr=ms;
	}
	PutLL(0, sl);
	PutLL(0, s);
	PutLL(0, sr);
	PutLL(0, msp);
	Send(0);
}

void node0()
{
	int i=0,from;
	long long int maxp=0,l,s,r,p;
	long long int msum=0;
	long long int pl=0,mpl=0;
	long long int ps=0,mps=0;
	long long int lsums[nodes];
	long long int ssums[nodes];
	long long int rsums[nodes];
	long long int psums[nodes];
	multiNode();
	for(;i<nodes;++i)
	{
		from=Receive(-1);
		l=GetLL(from);
		s=GetLL(from);
		r=GetLL(from);
		p=GetLL(from);
		lsums[from]=l;
		ssums[from]=s;
		rsums[from]=r;
		psums[from]=p;
		if(maxp<p)maxp=p;
	}
	ps=ssums[0];
	if(rsums[0]>ps)ps=rsums[0];
	if(mps<pl)mps=pl;
	pl=lsums[0];
	if(mpl<pl)mpl=pl;
	for(i=1;i<nodes;++i)
	{
		if(ps+lsums[i]>mps)mps=ps+lsums[i];
		
		ps+=ssums[i];
		if(rsums[i-1]+ssums[i]>ps)ps=rsums[i-1]+ssums[i];
		if(ps<0)ps=0;
		if(mps<ps)mps=ps;
		
		pl=lsums[i]+rsums[i-1];
		if(mpl<pl)mpl=pl;
	}
	if(msum<mpl)msum=mpl;
	if(msum<mps)msum=mps;
	if(msum<maxp)msum=maxp;
	printf("%lld\n",msum);
}

int main(void)
{
	N=Size();
	node=MyNodeId();
	nodes=NumberOfNodes();
	nSize=N/nodes;
	if(nodes*5>N)oneNode();
	else if(!node) node0();
	else multiNode();
	return 0;
}