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
#include "maklib.h"
#include "message.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
int n;
int proc,id;
LL sum=0,pre=0,suf=0,naj=0;
void licz(int po,int ko){
	F(i,po,ko){
		int pom = ElementAt(i+1);
		sum += pom;suf += pom;
		if(sum > pre)pre = sum;
		if(suf < 0)suf = 0;
		if(suf > naj)naj = suf;
	}
	if(id != 0){
		PutLL(0,sum);
		PutLL(0,pre);
		PutLL(0,suf);
		PutLL(0,naj);
		Send(0);
	}
}
void scal(){
	F(i,1,proc){
		Receive(i);
		LL sum2 = GetLL(i);
		LL pre2 = GetLL(i);
		LL suf2 = GetLL(i);
		LL naj2 = GetLL(i);
		naj = max(naj, max(naj2, suf + pre2));
		suf = max(suf + sum2, suf2);
	}
}
main(){
	n = Size();
	proc = NumberOfNodes();
	id = MyNodeId();
	int ile = (n+proc-1)/proc;
	licz(id * ile,min(n,(id+1)*ile));
	if(id == 0){
		scal();
		printf("%lld\n",naj);
	}
}