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 "message.h"
#include "kanapka.h"
#include <iostream>
#include <vector>
#include <numeric>

#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

using ll = long long;
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }

int main() {
    const int number_of_nodes = NumberOfNodes();
    const int my_node_id = MyNodeId();
    int n = GetN();
    {
        int l = (n *(ll)  my_node_id     ) / number_of_nodes;
        int r = (n *(ll) (my_node_id + 1)) / number_of_nodes;
        vector<ll> acc(r - l + 1);
        repeat (i, r - l) {
            acc[i+1] = acc[i] + GetTaste(l + i);
        }
        vector<ll> right_max(r - l + 1);
        repeat_reverse (i, r - l) {
            right_max[i] = max(right_max[i+1], acc[r-l] - acc[i]);
        }
        ll left_max = 0;
        ll both_max = 0;
        repeat (i, r - l + 1) {
            setmax(left_max, acc[i] - acc[0]);
            setmax(both_max, left_max + right_max[i]);
        }
        PutLL(0, acc[r-l] - acc[0]);
        PutLL(0, left_max);
        PutLL(0, right_max[0]);
        PutLL(0, both_max);
        Send(0);
    }
    if (my_node_id == 0) {
        vector<ll> total(number_of_nodes);
        vector<ll> left_max(number_of_nodes);
        vector<ll> right_max(number_of_nodes);
        vector<ll> both_max(number_of_nodes);
        repeat (node_id, number_of_nodes) {
            Receive(node_id);
            total[node_id] = GetLL(node_id);
            left_max[node_id] = GetLL(node_id);
            right_max[node_id] = GetLL(node_id);
            both_max[node_id] = GetLL(node_id);
        }
        ll total_of_total = whole(accumulate, total, 0ll);
        vector<ll> left_acc_max(number_of_nodes + 1); {
            ll acc = 0;
            repeat (i, number_of_nodes) {
                left_acc_max[i+1] = max(left_acc_max[i], acc + left_max[i]);
                acc += total[i];
            }
        }
        vector<ll> right_acc_max(number_of_nodes + 1); {
            ll acc = 0;
            repeat_reverse (i, number_of_nodes) {
                right_acc_max[i] = max(right_acc_max[i+1], acc + right_max[i]);
                acc += total[i];
            }
        }
        ll result = 0;
        setmax(result, total_of_total);
        repeat (i, number_of_nodes) {
            setmax(result, total_of_total - total[i] + both_max[i]);
        }
        repeat (i, number_of_nodes + 1) {
            setmax(result, left_acc_max[i] + right_acc_max[i]);
        }
        cout << result << endl;
    }
    return 0;
}