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
#include "maklib.h"
#include <message.h>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int myid   = MyNodeId();
const int nnodes = NumberOfNodes();

int main()
{
	long long N = Size();
	
	int poczatek = (N*myid) / nnodes;
	int koniec   = (N*(myid+1)) / nnodes;
	//printf("node id: %d (start=%d, end=%d)\n", myid, poczatek, koniec);
	
	// Dla każdego fragmentu, oprócz wyniku lokalnego, obliczamy maxsymalną sumę prefiksową i sufiksową.
	// Końcowy rozwiązanie budujemy w czasie O( nnodes ).
	
	long long sum = 0, maxprefix=0, maxsuffix=0, tmp=0, answer=0;
	for (int i=koniec-1; i>=poczatek; i--)
	{
		int x = ElementAt(i+1); 
		sum = sum + x;
		maxsuffix = max( maxsuffix, sum );
		tmp       = max( tmp+x, 0LL );
		answer    = max( answer, tmp );
	}
	sum = 0;
	for (int i=poczatek; i<koniec; i++)
	{
		int x = ElementAt(i+1); 
		sum = sum + x;
		maxprefix = max( maxprefix, sum );
	}
	
	if ( myid > 0 )
	{
		PutLL(0, sum);
		PutLL(0, maxprefix); PutLL(0, maxsuffix);
		PutLL(0, answer);
		Send(0);
	}
	else
	{
		// tablicujemy wszystkie wyniki
		vector<long long> sums( nnodes ), maxprefixes( nnodes ), 
		                  maxsuffixes( nnodes ), answers( nnodes );
		
		sums[ myid ]        = sum;
		maxprefixes[ myid ] = maxprefix;
		maxsuffixes[ myid ] = maxsuffix;
		answers[ myid ]     = answer;
		
		for (int i = 1; i < nnodes; i++)
		{
			int instancja = Receive(-1);
			sums[instancja]        = GetLL(instancja);
			maxprefixes[instancja] = GetLL(instancja);
			maxsuffixes[instancja] = GetLL(instancja);
			answers[instancja]     = GetLL(instancja);
		}
		
		//printf("Answers:\n"); for (int i=0; i<nnodes; i++) printf("%2d : (%3lld,%3lld,%3lld,%3lld)\n", i, sums[i], maxprefixes[i], maxsuffixes[i], answers[i]);
		
		sum = answer = 0;
		for (int i = 0; i<nnodes; i++)
		{
			answer = max( answer, answers[i] );
			answer = max( answer, sum + maxprefixes[i] );
			sum = max( sum + sums[i] , maxsuffixes[i] );
			answer = max( answer, sum );
		}
		printf("%lld\n", answer);
	}
	return 0;
}