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
83
84
85
86
87
88
89
90
91
92
93
94
95
#include "kanapka.h"
#include "message.h"
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

long long W[ 1000006 ];

void node_calc( ll id, ll nn ) {
    ll n = GetN();

    ll b = (id*n)/nn;
    ll e = ((id+1)*n)/nn;
    ll s, w, w2;

    w=s=0;
    for ( ll i=b; i<e; i++ ) {
        ll a = GetTaste(i);
        s += a;
        if (s>w) w=s;
        W[i-b] = w;
    }
    PutLL(0,s);
    PutLL(0,w);

    w2=w;
    w=s=0;
    for ( ll i=e-1; i>=b; i-- ) {
        if (W[i-b]+w>w2) w2=W[i-b]+w>w2;
        ll a = GetTaste(i);
        s += a;
        if (s>w) w=s;
    }
    PutLL(0,w);
    PutLL(0,w2);

}

void calc_sum( ll nn, ll nmul ) {
    ll Win[1024][4];
    ll W[1024][2];

    for ( ll _i=0; _i<nn; _i++ ) {
        ll _inst = Receive( -1 );
        for ( ll id=_inst*nmul; id<_inst*nmul+nmul; id++ ) {
            Win[id][0]=GetLL(_inst);
            Win[id][1]=GetLL(_inst);
            Win[id][2]=GetLL(_inst);
            Win[id][3]=GetLL(_inst);
        }
    }

    nn *= nmul;

    ll s,w,ww;
    s=w=0;
    for ( ll i=0; i<nn; i++ ) {
        W[i][1] = w;
        w=max(w,s+Win[i][1]);
        W[i][0] = s;
        s += W[2][0];
    }
    ww=w;
    s=w=0;
    for ( ll i=nn-1; i>=0; i-- ) {
        w=max(w,s+Win[i][2]);
        ww=max(ww,W[i][0]+s+Win[i][3]);
        ww=max(ww,w+W[i][1]);
    }

    printf("%lld\n",ww);
}


int main() {
    ll n = GetN();

    ll id = MyNodeId();
    ll nn = NumberOfNodes();

    ll nmul=1;
    if ( n/nn > 1e6 ) nmul = (n*2)/nn/1e6;

    for ( int i=0; i<nmul; i++ ) {
        node_calc( id+i, nn );
    }
    Send(0);

    if ( !id ) calc_sum( nn, 1 );

    return 0;
}