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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#include "kanapka.h"
#include "message.h"
using namespace std;
using ll = long long;

constexpr int nax = (5 * 1e8) / 100;

int h, id, n, dl, lo, hi;
vector< int > tab;
vector< ll > lew, pra;

int main()
{
    h = NumberOfNodes();
    id = MyNodeId();
    n = GetN();

    dl = (n + h - 1) / h;
    lo = min(n, dl * id);
    hi = min(dl * (id + 1) - 1, n - 1);

    ll sum = 0, prfmks = 0, suffmks = 0, prf = 0, suff = 0;
    ll prfm = 0, suffm = 0;

    tab.resize(dl);
    lew.resize(dl);
    pra.resize(dl);

    for (int i = lo; i <= hi; ++i)
        tab[i - lo] = GetTaste(i);

    for (int i = lo; i <= hi; ++i)
        sum += tab[i - lo];

    if (id - 1 >= 0)
    {
        Receive(id - 1);
        prf = GetLL(id - 1);
    }

    if (id + 1 < h)
    {
        PutLL(id + 1, prf + sum);
        Send(id + 1);
    }

    sum = 0;
    for (int i = lo; i <= hi; ++i)
        sum += tab[i - lo], prfm = max(prfm, sum + prf);

    if (id - 1 >= 0)
    {
        Receive(id - 1);
        prfmks = GetLL(id - 1);
    }

    if (id + 1 < h)
    {
        PutLL(id + 1, max(prfmks, prfm));
        Send(id + 1);
    }

    //suff

    if (id + 1 < h)
    {
        Receive(id + 1);
        suff = GetLL(id + 1);
    }

    if (id - 1 >= 0)
    {
        PutLL(id - 1, suff + sum);
        Send(id - 1);
    }

    sum = 0;
    for (int i = hi; i >= lo; --i)
        sum += tab[i - lo], suffm = max(suffm, sum + suff);

    if (id + 1 < h)
    {
        Receive(id + 1);
        suffmks = GetLL(id + 1);
    }

    if (id - 1 >= 0)
    {
        PutLL(id - 1, max(suffmks, suffm));
        Send(id - 1);
    }

    sum = 0;
    for (int i = lo; i <= hi; ++i)
        sum += tab[i - lo], lew[i - lo] = max(prfmks, prf + sum);

    sum = 0;
    for (int i = hi; i >= lo; --i)
        sum += tab[i - lo], pra[i - lo] = max(suffmks, suff + sum);

    for (int i = lo + 1; i <= hi; ++i)
        lew[i - lo] = max(lew[i - lo], lew[i - lo - 1]);

    for (int i = hi - 1; i >= lo; --i)
        pra[i - lo] = max(pra[i - lo], pra[i - lo + 1]);

    ll res = 0;

    if (lo <= hi)
        res = max(prf + pra[lo - lo], suff + lew[hi - lo]);

    for (int i = lo; i <= hi - 1; ++i)
        res = max(res, lew[i - lo] + pra[i - lo + 1]);

    if (id + 1 < h)
    {
        Receive(id + 1);
        res = max(res, GetLL(id + 1));
    }
    
//    for (int i = lo; i <= hi; ++i)
//        cerr << i << "= " << tab[i - lo] << ' ' << lew[i - lo] << ' ' << pra[i - lo] << '\n';
//
//    cerr << id << ' ' << lo << ' ' << hi << ' ' << res << ' ';
//    cerr << prf << ' ' << suff << ' ' << prfm << ' ' << suffm << '\n';
//    cerr << prfmks << ' ' << suffmks << '\n';
//
    if (id - 1 >= 0)
    {
        PutLL(id - 1, res);
        Send(id - 1);
    }

    if (id == 0)
        cout << res << '\n';
}