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

int main() {
	int I = MyNodeId();
	int N = Size();
	int M = NumberOfNodes();
	int BEGIN = 1LL*I*N/M+1;
	int END = 1LL*(I+1)*N/M;
	
	long long bestPrefix = 0, total = 0, bestSufix = 0, infix = 0, bestInfix = 0;
	
	for( int i = BEGIN; i <= END; i++ ) {
		int v = ElementAt(i);
		
		total += v;
		if( total > bestPrefix )
			bestPrefix = total;
			
		infix += v;
		if( infix < 0 )
			infix = 0;
		if( infix > bestInfix )
			bestInfix = infix;
		
	}
	
	bestSufix = infix;
	
	if( I > 0 ) {
		PutLL(0, bestInfix );
		PutLL(0, bestPrefix );
		PutLL(0, total );
		PutLL(0, bestSufix );
		Send(0);
	} else {
		long long prefix, sufix;
		for( int i = 1; i < M; i++ ) {
			Receive(i);
			infix = GetLL(i);
			prefix = GetLL(i);
			total = GetLL(i);
			sufix = GetLL(i);
			
			if( infix > bestInfix )
				bestInfix = infix;
		
			if( bestSufix + prefix > bestInfix )
				bestInfix = bestSufix + prefix;
				
			bestSufix += total;
			if( sufix > bestSufix )
				bestSufix = sufix;
		}
		printf("%lld\n", bestInfix);
	}
	
	return 0;
}