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

#include <algorithm>
#include <iostream>
using namespace std;

typedef long long LL;

struct KanBlock {
    LL s, mxb, mxe, mxeb; 
}; 

LL N, K, b, e;
int nodes, id;

void ProcessBlock(LL b, LL e)
{
    if (b >= e) return;

    KanBlock B;
    vector<LL> a;
    vector<LL> mxb;

    LL s = 0;
    LL mxs = 0;

    for (LL i = b; i < e; ++i) {
        LL t = GetTaste(i);
        a.push_back(t);
        s += t;
        mxb.push_back(max(mxs, s));
        mxs = mxb.back();
    }

    PutLL(0, s);
    PutLL(0, mxs);

    LL mxe = 0;
    LL mxeb = 0;
    LL se = 0;
    for (LL k = a.size() - 1; k >= 0; --k) {
        se += a[k];
        if (se > mxe) {
            mxe = se;
            mxeb = (k > 0 ? mxb[k-1] : 0LL);
        }
    }

    PutLL(0, mxe);
    PutLL(0, mxeb);
    Send(0);
}

void ReceiveData()
{
    vector<KanBlock> b(nodes);

    int an = 0;
    for (LL nr = 0; nr < N; nr += K) {
        int rid = Receive(-1);
        b[rid].s = GetLL(rid);
        b[rid].mxb = GetLL(rid);
        b[rid].mxe = GetLL(rid);
        b[rid].mxeb = GetLL(rid);
        ++an;
    }

    vector<LL> mxb;
    vector<LL> s;

    mxb.push_back(b[0].mxb);
    s.push_back(b[0].s);
    for (int i = 1; i < an; ++i) {
        mxb.push_back(max(mxb[i-1], s[i-1] + b[i].mxb));
        s.push_back(s[i-1] + b[i].s);
    }

    LL mxe = 0;
    LL se = 0;
    LL mx = max(s[an-1], 0LL);
    for (int i = an - 1; i >= 0; --i) {
        mxe = max(mxe, se + b[i].mxe);
        LL tmp = (i > 0 ? max(mxb[i-1], s[i-1] + b[i].mxeb) : b[i].mxeb);
        mx = max(mx, mxe + tmp);
        se += b[i].s;
    }

    cout << mx << endl;
}

int main() {
  N = GetN();
  nodes = NumberOfNodes();
  id = MyNodeId();
  K = (N + nodes - 1) / nodes;
  LL b = id * K;
  LL e = min(b + K, N);

  ProcessBlock(b, e);
  if (id == 0) ReceiveData();

  return 0;
}