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
#include "kanapka.h"
#include "message.h"

#include<assert.h>
#include<iostream>
#include<algorithm>
#include<limits>

int main() {
    int non=NumberOfNodes();
    int myNum=MyNodeId();

    long long N=GetN();
    long long intLen=N/non+1;
    long long mySum=0;
    long long myPrefMax=0; // pusty prefiks tez jest ok
    for( long long i=myNum*intLen; i<std::min((myNum+1)*intLen,N); ++i ) {
        mySum+=GetTaste(i);
        if(mySum > myPrefMax) myPrefMax=mySum;
    }
    for ( int i=0; i<non; ++i ) if(i!=myNum) { PutLL(i,mySum); Send(i); }

    long long sumLeft=0;
    long long sumRight=0;
    for ( int i=0; i<myNum; ++i ) {
       int instance = Receive(i);
       sumLeft += GetLL(instance);
    }
    for ( int i=myNum+1; i<non; ++i ) {
       int instance = Receive(i);
       sumRight += GetLL(instance);
    }

    long long pref=sumLeft+myPrefMax;
    for( int i=0; i<non; ++i) if(i > myNum) { PutLL(i,pref); Send(i); }

    long long bestPrefLeft=0;
    for( int i=0; i<myNum; ++i) {
        int instance = Receive(i);
        long long r=GetLL(instance);
        if (r>bestPrefLeft) bestPrefLeft=r;
    }

    long long bestPref;
    long long sum=0; bestPrefLeft-=sumLeft; long long suff=mySum; long long myResult=0;
    for( long long i=myNum*intLen; i<std::min((myNum+1)*intLen,N); ++i ) {
        long long taste=GetTaste(i);
        sum+=taste;
        suff-=taste;
        if(bestPrefLeft > sum) bestPref=bestPrefLeft;
        else {
           bestPref=sum;
           bestPrefLeft=sum;
        }
        if(myResult < bestPref + suff) myResult = bestPref+suff;
    }
    myResult+=sumLeft; myResult+=sumRight;

    if(myNum!=0) {
        PutLL(0,myResult);
        Send(0);
    }
    else {
        long long bestResult=myResult;
        for(int i=1; i<non; ++i) {
            int instance = Receive(i);
            long long res=GetLL(instance);
            if(res > bestResult) bestResult=res;
        }
        std::cout << bestResult << std::endl;
    }
    return 0;
}