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
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#include "kanapka.h"
#include "message.h"

using namespace std;

typedef long long ll;

int N, n, a, b, k;
vector<ll> pref, suff;

int main() {
    N = GetN();
    k = NumberOfNodes();

    a = int(ceil(double(N) / double(k))) * MyNodeId();
    b = min(a + int(ceil(double(N) / double(k))) - 1, N - 1);
    n = b - a + 1;

    if(a > b) {
        PutLL(0, -1);
        Send(0);
        return 0;
    }

    pref.resize(n);
    suff.resize(n);
    ll sum = 0;

    for(int i = a ; i <= b ; i++) {
        pref[i - a] = GetTaste(i);
        suff[i - a] = pref[i - a];
        sum += pref[i - a];
    }

    for(int i = 1 ; i < n ; i++)
        pref[i] += pref[i - 1];
    pref[0] = max(0LL, pref[0]);
    for(int i = 1 ; i < n ; i++)
        pref[i] = max(pref[i], pref[i - 1]);

    for(int i = n - 2 ; i >= 0 ; i--)
        suff[i] += suff[i + 1];
    suff[n - 1] = max(0LL, suff[n - 1]);
    for(int i = n - 2 ; i >= 0 ; i--)
        suff[i] = max(suff[i], suff[i + 1]);

    ll mid = max(suff[0], pref[n - 1]);
    for(int i = 1 ; i <= n - 1 ; i++)
        mid = max(mid, pref[i - 1] + suff[i]);

    PutLL(0, pref[n - 1]);
    Send(0);
    PutLL(0, suff[0]);
    Send(0);
    PutLL(0, mid);
    Send(0);
    PutLL(0, sum);
    Send(0);

    if(MyNodeId() != 0)
        return 0;

    vector<ll> p, s, t;
    vector<ll> sump, sums;

    for(int i = 0 ; i < k ; i++) {
        Receive(i);
        p.push_back(GetLL(i));
        if(p.back() == -1) {
            p.pop_back();
            continue;
		}

        Receive(i);
        s.push_back(GetLL(i));
        Receive(i);
        t.push_back(GetLL(i));
        Receive(i);
        sump.push_back(GetLL(i));
        sums.push_back(sump.back());
        
        //cout << i << " " << s.back() << " " << t.back() << " " << p.back() << endl;
    }

    k = p.size();

    for(int i = 1 ; i < k ; i++)
        sump[i] += sump[i - 1];
    for(int i = k - 2 ; i >= 0 ; i--)
        sums[i] += sums[i + 1];

	s[k - 1] = max(s[k - 1], 0LL);
	for(int i = k - 2; i >= 0 ; i--)
		s[i] = max(s[i] + sums[i + 1], s[i + 1]);
	p[0] = max(p[0], 0LL);
	for(int i = 1 ; i < k ; i++)
		p[i] = max(p[i - 1], p[i] + sump[i - 1]);

    ll res = max(p[k - 1], s[0]);
    for(int i = 1 ; i < k ; i++) {
        ll act = p[i - 1] + s[i];
        res = max(res, act);
    }

    for(int i = 0 ; i < k ; i++) {
        ll act = t[i];
        if(i > 0)
            act += sump[i - 1];
        if(i < n - 1)
            act += sums[i + 1];
        res = max(res, act);
    }

    printf("%lld\n", res);

    return 0;
}