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
107
108
109
#include <cstdio>
#include <vector>
#include <algorithm>
#include "message.h"
#include "kanapka.h"
using std::vector;
using std::min;
using ll = long long;

ll n;
int N, ID;


void leBrute() {
    long long sumall = 0, sum = 0, best = 0;
    for(int x, i = 0; i < n; ++i) {
        x = GetTaste(i);
        sum += x;
        sumall += x;
        if(sum > 0) sum = 0;
        if(best > sum) best = sum;
    }
    printf("%lld\n", sumall - best);
}

vector<int> t;
vector<ll>best;
vector<ll>beg;
vector<ll>end;
vector<ll>all;

void send_res(ll vbest, ll vbeg, ll vend, ll vall) {
    if(ID) {
        PutLL(0, vbest);
        PutLL(0, vbeg);
        PutLL(0, vend);
        PutLL(0, vall);
        Send(0);
    } else {
        best.push_back(vbest);
        beg.push_back(vbeg);
        end.push_back(vend);
        all.push_back(vall);
    }
}


ll val(int a, int b) {
    if(a == b) return best[a];
    ll res = end[a] + beg[b];
    for(int i = a + 1; i < b; ++i) res += all[i];
    return res;
}


void summary() {
    for(int i = 1; i < N; ++i) {
        Receive(i);
        best.push_back(GetLL(i));
        beg.push_back(GetLL(i));
        end.push_back(GetLL(i));
        all.push_back(GetLL(i));
    }
    ll mn = 0;
    ll sumall = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = i; j < N; ++j)
            mn = min(mn, val(i, j));
        sumall += all[i];
    }
    printf("%lld\n", sumall - mn);
}


void process_slice() {
    int A = ID * n / N, B = (ID + 1) * n / N - 1;
    t.resize(B - A + 1);
    for(int i = A; i <= B; ++i)
        t[i - A] = GetTaste(i);
    n = B - A + 1;

    ll vbest = 0, vbeg = 0, vend = 0, vall = 0, sum = 0;
    for(int i = 0; i < n; ++i) {
        sum += t[i];
        vall += t[i];
        if(vbeg > vall) vbeg = vall;
        if(sum > 0) sum = 0;
        if(vbest > sum) vbest = sum;
    }
    sum = 0;
    for(int i = n - 1; i >= 0; --i) {
        sum += t[i];
        if(vend > sum) vend = sum;
    }
    send_res(vbest, vbeg, vend, vall);
    if(!ID) summary();
}

int main() {
    N = NumberOfNodes();
    ID = MyNodeId();
    n = GetN();
    if(n <= 1000) {
        if(ID == 0) leBrute();
        return 0;
    }

    process_slice();
}