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
// Krzysztof Piesiewicz
// Maksymalna podtablica PA 2014
#include "message.h"
#include "maklib.h"
#include <algorithm>
#include <cstdio>
#define LL (long long)
using namespace std;

const int DB = 0;

int id, n, size, p, k, curr;
long long all, bestBegin, bestEnd, res;

int main() {
	size = Size();
	n = NumberOfNodes();
	id = MyNodeId();
	p = 1 + LL(id) * size / n;
	k = 1 + LL(id + 1) * size / n;
	
	for( int i = p; i < k; i++ ) {
		curr = ElementAt( i );
		all += curr;
		bestBegin = max( bestBegin, all );
		bestEnd = max( 0LL, bestEnd + curr );
		res = max( res, bestEnd );
	}
	if( DB ) printf( "id %d, p %d, k %d, all %Ld, beg %Ld, end %Ld\n", id, p, k, all, bestBegin, bestEnd );
	
	if( id > 0 ) {
		PutLL( 0, res );
		PutLL( 0, all );
		PutLL( 0, bestBegin );
		PutLL( 0, bestEnd );
		Send( 0 );
	}
	else {
		long long sum[ n + 7 ], begin[ n + 7 ], end[ n + 7 ];
		sum[ 0 ] = 0;
		begin[ 0 ] = bestBegin;
		end[ 0 ] = bestEnd;
		
		for( int j = 1; j < n; j++ ) {
			int inst = Receive( -1 );
			res = max( res, GetLL( inst ) );
			sum[ inst ] = GetLL( inst );
			begin[ inst ] = GetLL( inst );
			end[ inst ] = GetLL( inst );
		}
		bestBegin = begin[ n ] = end[ n ] = sum[ n ] =  0;
		for( int j = 0; j <= n; j++ ) {
			res = max( res, bestBegin + begin[ j ] );
			bestBegin = max( bestBegin + sum[ j ], end[ j ] );
		}
		printf( "%Ld\n", res );
	}
	return 0;
}