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
#include "kanapka.h"
#include "message.h"
#include <bits/stdc++.h>

using namespace std;

int main() {
  int n = GetN();
  int m = NumberOfNodes();
  int block_size = (n + m - 1) / m;
  int l = block_size * MyNodeId();
  int r = min(n, block_size * (MyNodeId() + 1));
  long long prefix = 0;
  long long sum_prefix = 0;
  for (int i = l; i < r; ++i) {
    sum_prefix += GetTaste(i);
    prefix = min(prefix, sum_prefix);
  }
  long long suffix = 0;
  long long sum_suffix = 0;
  for (int i = r - 1; i >= l; --i) {
    sum_suffix += GetTaste(i);
    suffix = min(suffix, sum_suffix);
  }
  long long answer = 0;
  long long current = 0;
  for (int i = l; i < r; ++i) {
    current += GetTaste(i);
    if (current > 0) {
      current = 0;
    } else {
      answer = min(answer, current);
    }
  }
  long long sum = sum_prefix;
  if (MyNodeId()) {
    PutLL(0, prefix);
    PutLL(0, suffix);
    PutLL(0, answer);
    PutLL(0, sum);
    Send(0);
  } else {
    for (int i = 1; i < m; ++i) {
      Receive(i);
      long long new_prefix = GetLL(i);
      long long new_suffix = GetLL(i);
      long long new_answer = GetLL(i);
      long long new_sum = GetLL(i);
      answer = min(answer, new_answer);
      answer = min(answer, suffix + new_prefix);
      prefix = min(prefix, sum + new_prefix);
      suffix = min(new_sum + suffix, new_suffix);
      sum += new_sum;
    }
    printf("%lld\n", sum - answer);
  }
  return 0;
}