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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define FORE(i, t) for(typeof(t.begin())i=t.begin();i!=t.end();++i)
#define SZ(x) int((x).size())
#define REP(i, n) for(int i=0,_=(n);i<_;++i)
#define FOR(i, a, b) for(int i=(a),_=(b);i<=_;++i)
#define FORD(i, a, b) for(int i=(a),_=(b);i>=_;--i)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#include "message.h"
#include "kanapka.h"

const int INF = 1e9 + 9;
const int MAX_NODES = 103;

ll n = GetN();
int me = MyNodeId();
int nodes_count = NumberOfNodes();

void solve_part() {
    ll a = n * me / nodes_count;
    ll b = n * (me + 1) / nodes_count - 1;
    ll sum = 0;
    ll best = 0;
    ll best_left = 0;
    ll best_right = 0;
    ll sum_left = 0;
    ll sum_right = 0;
    FOR (i, a, b) {
        ll taste = GetTaste(i);
        sum_left += taste;
        best_left = max(best_left, sum_left);
    }
    sum = sum_left;
    FORD (i, b, a) {
        ll taste = GetTaste(i);
        sum_left -= taste;
        sum_right += taste;
        best_right = max(best_right, sum_right);
        best = max(best, best_right + sum_left);
    }
    PutLL(0, sum);
    PutLL(0, best);
    PutLL(0, best_left);
    PutLL(0, best_right);
    Send(0);
}

void merge_parts() {
    if (me != 0) {
        return;
    }
    ll part_sums[MAX_NODES] = {};
    ll part_bests[MAX_NODES] = {};
    ll part_best_lefts[MAX_NODES] = {};
    ll part_best_rights[MAX_NODES] = {};
    REP (node, nodes_count) {
        Receive(node);
        part_sums[node + 1] = GetLL(node);
        part_bests[node + 1] = GetLL(node);
        part_best_lefts[node + 1] = GetLL(node);
        part_best_rights[node + 1] = GetLL(node);
    }
//    FOR (i, 1, nodes_count) {
//        printf("%lld\t%lld\t%lld\t%lld\n", part_sums[i], part_bests[i], part_best_lefts[i], part_best_rights[i]);
//    }
//    puts("");
    ll best_lefts[MAX_NODES] = {};
    ll best_rights[MAX_NODES] = {};
    ll sum_lefts[MAX_NODES] = {};
    ll sum_rights[MAX_NODES] = {};
    FOR (i, 1, nodes_count) {
        sum_lefts[i] = sum_lefts[i - 1] + part_sums[i];
        best_lefts[i] = max(best_lefts[i - 1], sum_lefts[i - 1] + part_best_lefts[i]);
    }
    FORD (i, nodes_count, 1) {
        sum_rights[i] = sum_rights[i + 1] + part_sums[i];
        best_rights[i] = max(best_rights[i + 1], sum_rights[i + 1] + part_best_rights[i]);
    }
//    FOR (i, 1, nodes_count) {
//        printf("%lld\t%lld\t%lld\t%lld\n", sum_lefts[i], sum_rights[i], best_lefts[i], best_rights[i]);
//    }
    ll result = 0;
    FOR (i, 1, nodes_count) {
        ll best = max(max(best_lefts[i - 1] + best_rights[i], best_lefts[i] + best_rights[i + 1]),
                      part_bests[i] + sum_lefts[i - 1] + sum_rights[i + 1]);
        result = max(result, best);
    }
    printf("%lld\n", result);
}

void inline one() {
    solve_part();
    merge_parts();
}

int main() {
    //int z; scanf("%d", &z); while(z--)
    one();
}