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
120
121
122
123
124
#include "maklib.h"
#include "message.h"
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector <long long int> psum;
vector <pair <long long int, long long int> > prsu;
vector <long long int> razem;

int rozm(int q)
{
 int r=1;

 	while(r<q+q)
		r=(r<<1);

 return r;
}

void podc(long long int le, long long int c, long long int qm, long long int qp, long long int qs, long long int qw)
{
 int r=(rozm(le)>>1);
 int w=r+c;
 
 razem[w]=qw;
 psum[w]=qm;
 prsu[w].first=qp;
 prsu[w].second=qs;
 w=(w>>1);

 	while(w>0)
 	{
	 psum[w]=max(max(psum[w+w], psum[w+w+1]), prsu[w+w+1].first+prsu[w+w].second);
	 prsu[w].first=max(prsu[w+w].first, razem[w+w]+prsu[w+w+1].first);
	 prsu[w].second=max(prsu[w+w+1].second, razem[w+w+1]+prsu[w+w].second);
	 razem[w]=razem[w+w]+razem[w+w+1];
	 w=(w>>1);
	}
}

int main()
{
	bool czyp;
	long long int n, x, y, sz, pp, kp, im, ip, is, iw, um, up, us, uw;
	
	n=1LL*Size();
	y=0LL;
	im=0LL;
	ip=0LL;
	is=0LL;
	iw=0LL;
	czyp=true;
	
	if(n>=NumberOfNodes())
	{
	 pp=1LL+(1LL*MyNodeId()*n)/(1LL*NumberOfNodes());
	 kp=(1LL*(MyNodeId()+1)*n)/(1LL*NumberOfNodes());
	}
	else
	{
	 pp=1;
	 kp=n;
	}
	
	if(n>=NumberOfNodes() || MyNodeId()==0)
	{
	 	for(int i=pp;i<=kp;i++)
	 	{
	 	 x=1LL*ElementAt(i);
	 	 iw=iw+x;
	 	 
	 	 	if(y>0LL)
	 	 		y=y+x;
	 	 	else
	 	 		y=x;
	 	 		
	 	 	if(x<0LL)
	 	 		czyp=false;
	 	 	
	 	 	if(czyp==true)
	 	 		ip=ip+x;
	 	 
	 	 im=max(im, y);
	 	 is=max(max(is+x, x), 0LL);
	 	}
	}
 	
 	sz=rozm(NumberOfNodes());
	psum.resize(sz, 0LL);
	prsu.resize(sz, make_pair(0LL, 0LL));
	razem.resize(sz, 0LL);
 	
 	if(MyNodeId()>0)
 	{
 	 PutLL(0, im);
 	 PutLL(0, ip);
 	 PutLL(0, is);
 	 PutLL(0, iw);
 	 Send(0);
 	}
 	else
 	{
 	 podc(1LL*NumberOfNodes(), 1LL*MyNodeId(), im, ip, is, iw);
 	 
 	 	for(int j=1;j<NumberOfNodes();j++)
 	 	{
      	 Receive(j);
      	 um=GetLL(j);
 		 up=GetLL(j);
 		 us=GetLL(j);
 		 uw=GetLL(j);
 		 podc(1LL*NumberOfNodes(), 1LL*j, um, up, us, uw);
      	}
      	
     printf("%lld\n", psum[1]);
 	}		
 	
    return 0;
}