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
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include "message.h"
#include "maklib.h"
using namespace std;

namespace {

typedef long long LL;

struct Result {
  LL offset;
  LL smallest;
  LL largest;
  LL best;
};

const int ELEMENTS_PER_NODE = 1000000;
int NUMBER_OF_NODES;
int ACTIVE_NODES;
int MY_NODE_ID;
int NELEMENTS;



void Initialize() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  NUMBER_OF_NODES = NumberOfNodes();
  MY_NODE_ID = MyNodeId();
  NELEMENTS = Size();

  ACTIVE_NODES = min((NELEMENTS + ELEMENTS_PER_NODE-1) / ELEMENTS_PER_NODE, NUMBER_OF_NODES);
  assert(ACTIVE_NODES >= 1 && ACTIVE_NODES <= NUMBER_OF_NODES);
}

int StartAt(int node) {
  return 1 + static_cast<int>(static_cast<LL>(NELEMENTS) * node / ACTIVE_NODES);
}

Result Compute(int a, int b) {
  Result res;
  res.offset = 0;
  res.smallest = 0;
  res.largest = 0;
  res.best = 0;
  for(int i=a;i<b;++i) {
    int x = ElementAt(i);
    res.offset += x;
    res.smallest = min(res.smallest, res.offset);
    res.largest = max(res.largest, res.offset);
    res.best = max(res.best, res.offset - res.smallest);
  }
  return res;
}

Result Add(const Result &a, const Result &b) {
  Result res;
  res.offset = a.offset + b.offset;
  res.smallest = min(a.smallest, a.offset + b.smallest);
  res.largest = max(a.largest, a.offset + b.largest);
  res.best = max(max(a.best, b.best), a.offset + b.largest - a.smallest);
  return res;
}

void SendResult(int target, const Result &res) {
  PutLL(target, res.offset);
  PutLL(target, res.smallest);
  PutLL(target, res.largest);
  PutLL(target, res.best);
  Send(target);
}

Result ReceiveResult(int target) {
  int ret = Receive(target);
  assert(ret == target);
  Result res;
  res.offset = GetLL(target);
  res.smallest = GetLL(target);
  res.largest = GetLL(target);
  res.best = GetLL(target);
  return res;
}

} // namespace

int main() {
  Initialize();
  if (MY_NODE_ID>=ACTIVE_NODES) return 0;

  Result res = Compute(StartAt(MY_NODE_ID), StartAt(MY_NODE_ID+1));
  if (MY_NODE_ID == 0) {
    for(int i=1;i<ACTIVE_NODES;++i) {
      Result res2 = ReceiveResult(i);
      res = Add(res, res2);
    }
    cout << res.best << '\n';
  } else {
    SendResult(0, res);
  }
}