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
#include "kanapka.h"
#include "message.h"
#include <cstdio>
#include <algorithm>
using std::max;
using std::min;

#define ll long long

const int pSize = 1e6;
int N, Id;
ll n;
ll maxNt[pSize + 10];
ll t[pSize + 10];

ll count(int from, int to) {
    ll max0 = 0, maxN = 0, sum = 0, result = 0;
    maxNt[to - from] = 0;

    for(int i = to - 1; i >= from; --i) {
        sum += t[i - from] = GetTaste(i);
        maxNt[i - from] = max(sum, maxNt[i + 1 - from]);
        maxN = max(sum, maxN);
    }
    sum = 0;
    result = max(result, maxNt[0]);
    for(int i = from; i < to; ++i) {
        sum += t[i - from];
        max0 = max(sum, max0);
        result = max(result, max0 + maxNt[i + 1 - from]);
    }

    PutLL(0, max0);
    PutLL(0, maxN);
    PutLL(0, sum);
    PutLL(0, result);
    Send(0);
    return result;
}


ll count_result() {
    ll result = 0, max0 = 0, maxN = 0, sum = 0;
    ll result_here, max0_here, maxN_here, sum_here;
    ll result_tmp, max0_tmp, maxN_tmp, sum_tmp;
    for(ll i = 0; i * pSize <= n; ++i) {
        Receive(i % N);
        max0_here   = max0;
        maxN_here   = maxN;
        sum_here    = sum;
        result_here = result;

        max0_tmp   = GetLL(i % N);
        maxN_tmp   = GetLL(i % N);
        sum_tmp    = GetLL(i % N);
        result_tmp = GetLL(i % N);

        max0 = max(max0_here, sum_here + max0_tmp);
        maxN = max(maxN_tmp, sum_tmp + maxN_here);
        sum  = sum_here + sum_tmp;
        result = max0_here + maxN_tmp;
        result = max(result, result_here + sum_tmp);
        result = max(result, sum_here + result_tmp);
    }
    printf("%lld\n", result);
}

int main() {
    N = NumberOfNodes();
    Id = MyNodeId();
    n = GetN();

    for(ll i = 0; pSize * (i * N + Id) <= n; ++i)
        count(pSize * (i * N + Id), min(n, pSize * (i * N + Id + 1)));
    if(Id)
        return 0;

    count_result();
    return 0;
}