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

#include <iostream>
#include <cstdio>
#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 * (long long)my_node_id) / number_of_nodes;
    int r = (n * (long long)(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]);
        }
        printf("%lld\n", result);
    }
    return 0;
}