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
#include <algorithm>
#include <iostream>
using namespace std;

#include "message.h"
#include "kanapka.h"
typedef long long ll;

const ll SMALL = 1000; // threshold to run on multiple instances
int my_id, nodes;
ll N, L, R;

ll total(ll b, ll e) {
  ll res = 0;
  for (ll i = b; i < e; i++) res += GetTaste(i);
  return res;
}

ll worst(ll b, ll e) {
  ll res = 0;
  ll w = 0;
  for (ll i = b; i < e; i++) {
    w += GetTaste(i);
    res = min(res, w);
    w = min(0LL, w);
  }
  return res;
}

ll worst_from_left(ll b, ll e) {
  ll res = 0;
  ll w = 0;
  for (ll i = b; i < e; i++) {
    w += GetTaste(i);
    res = min(res, w);
  }
  return res;
}

ll worst_from_right(ll b, ll e) {
  ll res = 0;
  ll w = 0;
  for (ll i = e-1; i >= b; i--) {
    w += GetTaste(i);
    res = min(res, w);
  }
  return res;
}

ll solve() {
  ll t[nodes], ct[nodes], wfr[nodes], wfl[nodes];
  ll ww = 0;

  for (int i = 0; i < nodes; i++) {
    Receive(i);
    t[i] = GetLL(i);
    ww = min(ww, GetLL(i));
    wfr[i] = GetLL(i);
    wfl[i] = GetLL(i);
  }

  ct[0] = t[0];
  for (int i = 1; i < nodes; i++) {
    ct[i] = ct[i-1] + t[i];
  }
  ll tt = ct[nodes-1];

  ll ws = 0;
  for (int i = 0; i < nodes-1; i++) {
    for (int j = i+1; j < nodes; j++) {
      ll wb = wfr[i] + wfl[j] + (ct[j-1] - ct[i]);
      ws = min(ws, wb);    
    }
  }

  cerr << "total=" << tt << " worst(in_part)=" << ww << " worst(split)=" << ws << '\n';
  return tt - min(ww, ws);
}

int main() {
  my_id = MyNodeId();
  nodes = NumberOfNodes();
  N = GetN();

  if (N < SMALL) {
    if (my_id > 0) return 0;
    ll t = total(0, N), w = worst(0, N);
    cerr << "total=" << t << " worst(in_part)=" << w << '\n';
    cout << (t-w) << '\n';
    return 0;
  }
  
  ll size = N / nodes;
  L = my_id * size;
  R = L + size;
  if (my_id + 1 == nodes) R = N;
  cerr << "[" << L << ", " << R << ")\n";

  PutLL(0, total(L, R));
  PutLL(0, worst(L, R));
  PutLL(0, worst_from_right(L, R));
  PutLL(0, worst_from_left(L, R));
  Send(0);

  if (my_id > 0) return 0;

  cout << solve() << '\n';
  return 0;
}