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

using namespace std;

typedef long long LL;

vector<LL> sums, prefs, sufs;
LL global_best = 0;

ostream & operator<<(ostream & out, vector<LL> V) {
    out << "[";
    for(auto v : V) out << v << ", ";
    out << "]";
    return out;
}

void solve() {
    int p = NumberOfNodes();
    for(int i = 1; i < p; i++) {
        assert(Receive(i) == i);
        LL best = GetLL(i);
        global_best = max(global_best, best);
        LL pref = GetLL(i);
        prefs[i] = pref;
        LL suf = GetLL(i);
        sufs[i] = suf;
        LL sum = GetLL(i);
        sums[i] = sum;
    }
    //cout << prefs << endl;
    //cout << sufs << endl;
    //cout << sums << endl;
    //printf("%lld\n", global_best);
    for(int i = 0; i < p; i++) {
        LL cur = sufs[i];
        for(int j = i+1; j < p; j++) {
            //printf("[%d, %d]: %lld\n", i, j, cur + prefs[j]);
            global_best = max(global_best, cur + prefs[j]);
            cur += sums[j];
        }
    }
    printf("%lld\n", global_best);
}

int main() {
    int n = Size();
    int p = NumberOfNodes();
    sums.resize(p);
    prefs.resize(p);
    sufs.resize(p);
    int k = MyNodeId();
    int split_size = (n + p - 1) / p;
    long long best = 0, bestpref = 0, bestcur = 0, sum = 0;
    for(int i = split_size * k + 1; i <= split_size*(k+1) and i <= n; i++) {
        int val = ElementAt(i);
        sum += val;
        bestpref = max(sum, bestpref);
        bestcur = max(0LL, bestcur + val);
        best = max(bestcur, best);
    }
    long long bestsuf = 0, sufsum = 0;
    for(int i = min(split_size * (k+1), n); i >= split_size*k + 1; i--) {
        int val = ElementAt(i);
        sufsum += val;
        bestsuf = max(sufsum, bestsuf);
    }
    //printf("%d %d: %lld %lld %lld %lld\n", split_size * k + 1, split_size*(k+1), best, bestpref, bestsuf, sum);
    if (k == 0) {
        global_best = max(global_best, best);
        prefs[0] = bestpref;
        sufs[0] = bestsuf;
        sums[0] = sum;
        solve();
    } else {
        PutLL(0, best);
        PutLL(0, bestpref);
        PutLL(0, bestsuf);
        PutLL(0, sum);
        Send(0);
    }
    return 0;
}