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
80
81
82
#include<stdio.h>
#include<vector>
#include<algorithm>
#include "kanapka.h"
#include "message.h"
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc scanf
#define pr printf

using namespace std;

ll GT(int x){
    return GetTaste((ll)(x));
}

int main (){
    int n=(int)(GetN());
    int b=0;
    int e=n;
    const int id=MyNodeId();
    const int nn=NumberOfNodes();
    int p=n/nn;
    b=p*id;
    if(id!=nn-1)e=p*(id+1);
    ll pp=0,mi=0;
    for(int i=b;i<e;i++){
        pp+=GT(i);
        mi=min(mi,pp);
    }
    ll cm=0,cp=0,su;
    if(id>0){
        PutLL(0,mi);
        PutLL(0,pp);
        Send(0);
        Receive(0);
        cm=GetLL(0);
        cp=GetLL(0);
    }
    if(id==0){
        ll p1[nn],p2[nn+1];
        p1[0]=pp;
        for(int i=1;i<nn;i++){
            Receive(i);
            p2[i]=GetLL(i);
            p1[i]=GetLL(i);
        }
        for(int i=1;i<nn;i++)p1[i]+=p1[i-1];
        for(int i=1;i<=nn;i++)p2[i]+=p1[i-1];
        for(int i=nn-1;i>0;i--)p2[i]=min(p2[i],p2[i+1]);
        for(int i=1;i<nn;i++){
            PutLL(i,p2[i+1]);
            PutLL(i,p1[i-1]);
            Send(i);
        }
        cm=p2[1];
        su=p1[nn-1];
    }
    pp+=cp;
    ll w=0;
    for(int i=e-1;i>=b;i--){
        w=min(w,cm-pp);
        cm=min(pp,cm);
        pp-=GT(i);
    }
    if(id==0){
        w=min(w,cm);
        for(int i=1;i<nn;i++){
            Receive(i);
            w=min(w,GetLL(i));
        }
        printf("%lld",su-w);
    }
    else{
        PutLL(0,w);
        Send(0);
    }
    return 0;
}