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

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

struct Result {
  long long bl, total, br, inside;
};

long long tmp[10000000];

long long IT = 10000000;

Result solve(int left, int right) {
  long long BL = 0, BR = 0, total = 0;
  long long cl = 0, cr = 0;
  for (int i=left; i<right; ++i) {
    long long current = GetTaste(i);
    cl += current;
    BL = max(BL, cl);
    total += current;
    tmp[i-left] = BL;
  }

  long long inside = 0;
  for (int i=right-1; i>=left; --i) {
    long long current = GetTaste(i);
    cr += current;
    BR = max(BR, cr);
    if (i > left) {
      inside = max(inside, tmp[i-left-1] + BR);
    }
  }

  return {BL, total, BR, inside};
}

void solveMulti(int count, int nodes) {
  long long totalL[count], totalR[count], bestL[count], bestR[count];
  cerr << "start multi " << count << endl;
  Result r[count];
  for (int i=0; i<count; ++i) {
    int ci = i % nodes;
    Receive(ci);
    r[i].bl = GetLL(ci);
    r[i].total = GetLL(ci);
    r[i].br = GetLL(ci);
    r[i].inside = GetLL(ci);
  }

  long long best = 0;
  totalL[0] = r[0].total;
  bestL[0] = max(0ll, r[0].bl);
  for (int i=1; i<count; ++i) {
    totalL[i] = totalL[i-1] + r[i].total;
    bestL[i] = max(bestL[i-1], totalL[i-1] + r[i].bl);
  }

  int last = count-1;
  totalR[last] = r[last].total;
  bestR[last] = max(0ll, r[last].br);
  for (int i=last-1; i>=0; --i) {
    totalR[i] = totalR[i+1] + r[i].total;
    bestR[i] = max(bestR[i+1], totalR[i+1] + r[i].br);
  }


  long long ts = 0;
  for (int i=0; i<count; ++i) {
    ts += r[i].total;
    best = max(best, (i == 0 ? 0 : totalL[i-1]) + r[i].bl + (i+1 < count ? bestR[i+1] : 0));
    best = max(best, (i == 0 ? 0 : bestL[i-1]) + r[i].br + (i+1 < count ? totalR[i+1] : 0));
    best = max(best, (i == 0 ? 0 : totalL[i-1]) + r[i].inside + (i+1 < count ? totalR[i+1] : 0));
  }

  cout << max(ts, best) << endl;
}

int main() {
  long long N = GetN();
  int id = MyNodeId();
  int nodes = NumberOfNodes();
  int iters = (N + (IT-1)) / IT;


  for (int i=id; i<iters; i+=nodes) {
    cerr << "CMP " << i << " iters " << iters << endl;
    int left = i*IT;
    int right = min(i*IT+IT, N);
    cerr << "ID[" << (id) << "] -- [" << left << "," << right <<  "]" << endl;
    cerr << "SOLVE " << left << " : " << right << endl;
    Result r = solve(left, right);
    PutLL(0, r.bl);
    PutLL(0, r.total);
    PutLL(0, r.br);
    PutLL(0, r.inside);
    Send(0);
  }


  if (id == 0) {
    solveMulti(iters, nodes);
  }

  return 0;
}