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

using namespace std;

typedef long long i64;

struct monoid_t {
    i64 total;
    i64 max_prefix;
    i64 max_suffix;
    i64 result;
};

monoid_t zero() {
    return {0, 0, 0, 0};
}

monoid_t merge(const monoid_t &x, const monoid_t &y) {
    monoid_t r;
    r.total = x.total + y.total;
    r.max_prefix = max(x.max_prefix, x.total + y.max_prefix);
    r.max_suffix = max(y.max_suffix, y.total + x.max_suffix);
    r.result = max(max(
        max(r.total, x.max_prefix + y.max_suffix),
        max(x.total + y.result, x.result + y.total)
    ), 0LL);
    return r;
}

monoid_t inject(i64 value) {
    monoid_t r;
    r.total = value;
    r.max_prefix = max(0LL, value);
    r.max_suffix = max(0LL, value);
    r.result = max(0LL, value);
    return r;
}

void send(int target, const monoid_t& m) {
    PutLL(target, m.total);
    PutLL(target, m.max_prefix);
    PutLL(target, m.max_suffix);
    PutLL(target, m.result);
    Send(target);
}

monoid_t receive(int source) {
    monoid_t r;
    Receive(source);
    r.total = GetLL(source);
    r.max_prefix = GetLL(source);
    r.max_suffix = GetLL(source);
    r.result = GetLL(source);
    return r;
}

int main() {
    int p = MyNodeId();
    int pn = NumberOfNodes();
    
    i64 lower = ((GetN() - 1) * p) / pn + (p == 0 ? 0 : 1);
    i64 upper = ((GetN() - 1) * (p + 1)) / pn;
    
    monoid_t m = zero();
    for (i64 i = lower; i <= upper; ++i) {
        m = merge(m, inject(GetTaste(i)));
    }
    
    if (p == 0) {
        for (int i = 1; i < pn; ++i) {
            m = merge(m, receive(i));
        }
        printf("%lld\n", m.result);
    } else {
        send(0, m);
    }

    return 0;
}