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

using namespace std;
using ll = long long;

const ll INF = 1e18;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int ile = NumberOfNodes();
    int n = GetN();
    ile = min(ile, n);
    int id = MyNodeId();
    if (id >= n) return 0;
    int m = (n + ile - 1) / ile;
    int l = m * id, r = min(n - 1, l + m - 1);

    //cout << l << " " << r << " " << m << "\n";

    ll makspref = 0, makssuf = 0, sum = 0;
    for (int i = l; i <= r; i++) {
        sum += GetTaste(i);
        makspref = max(makspref, sum);
    }

    sum = 0;
    for (int i = r; i >= l; i--) {
        sum += GetTaste(i);
        makssuf = max(makssuf, sum);
    }

    //cout << sum << "\n";
    ll pref = 0;
    ll suf = 0;
    ll bestpref = 0;
    ll bestsuf = 0;

    if (id) {
        Receive(id - 1);
        pref = GetLL(id - 1);
        bestpref = GetLL(id - 1);
    }

    if (id < ile - 1) {
        PutLL(id + 1, pref + sum);
        PutLL(id + 1, makspref + pref);
        Send(id + 1);
    }

    if (id < ile - 1) {
        Receive(id + 1);
        suf = GetLL(id + 1);
        bestsuf = GetLL(id + 1);
    }

    if (id) {
        PutLL(id - 1, suf + sum);
        PutLL(id - 1, makssuf + suf);
        Send(id - 1);
    }

    vector<ll> maks(m);
    maks[0] = sum = GetTaste(l);
    for (int i = l + 1; i <= r; i++)
    {
        sum += GetTaste(i);
        maks[i - l] = max(maks[i - l - 1], sum);
    }

    //cout << "prefsuf " << pref << " " << suf << "\n";
    //cout << "best: " << bestpref << " " << bestsuf << "\n";
    ll res = max({pref + makspref + bestsuf, suf + makssuf + bestpref, bestpref + bestsuf});

    sum = suf;
    for (int i = r; i > l; i--) {
        sum += GetTaste(i);
        res = max(res, maks[i - l - 1] + pref + sum);
    }

    //cout << "RES: " << res << "\n";
    if (id) {
        PutLL(0, res);
        Send(0);
        return 0;
    }

    for (int i = 1; i < ile; i++) {
        Receive(i);
        res = max(res, GetLL(i));
    }

    cout << res << "\n";
}