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
#include "kanapka.h"
#include "message.h"
#include <cstdio>
#include <algorithm>
typedef long long LL;
using namespace std;

int NODES, ID;

void chunk() {
  int n = GetN(), len = n/NODES;
  int a = ID * len;
  int b = (ID==NODES-1) ? n : a + len;

  // printf("%d\n", n);
  // for (int i=0; i<n; ++i) printf("%lld ", GetTaste(i));

  LL total = 0, lmax = 0, sub = 0, bestsub = 0;
  for (int i=a; i<b; ++i) {
    LL x = GetTaste(i);
    lmax = max(lmax, total += x);
    if ((sub += x) < 0) bestsub = min(bestsub, sub);
    else sub = 0;
  }

  total = 0;
  LL rmax = 0;
  for (int i=b-1; i>=a; --i) {
    rmax = max(rmax, total += GetTaste(i));
  }

  PutLL(0, total);
  PutLL(0, bestsub);
  PutLL(0, lmax);
  PutLL(0, rmax);
  Send(0);
}

void master() {
  LL total[NODES], sub[NODES], lmax[NODES], rmax[NODES];

  for (int i=0; i<NODES; ++i) {
    Receive(i);
    total[i] = GetLL(i);
    sub[i] = GetLL(i);
    lmax[i] = GetLL(i);
    rmax[i] = GetLL(i);
    // printf("== %lld %lld %lld\n", total[i], lmax[i], rmax[i]);
  }

  LL sum = 0;
  for (int i=0; i<NODES; ++i) {
    lmax[i] += sum;
    sum += total[i];
  }
  sum = 0;
  for (int i=NODES-1; i>=0; --i) {
    rmax[i] += sum;
    sum += total[i];
  }

  LL res = sum;
  for (int i=0; i<NODES; ++i) {
    res = max(res, sum - sub[i]);
  }
  for (int i=0; i<=NODES; ++i) {
    res = max(res, (i>0 ? lmax[i-1] : 0) + (i<NODES ? rmax[i] : 0));
  }

  printf("%lld\n", res);
}

int main() {
  NODES = NumberOfNodes();
  ID = MyNodeId();
  chunk();
  if (ID == 0) master();
  return 0;
}