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
#include <bits/stdc++.h>
#include "kanapka.h"
#include "message.h"
using namespace std;
typedef long long ll;

pair<ll, ll> divide(ll n) {
  auto f = [](ll n, int i, int k) { return n * i / k; };
  return make_pair(f(n, MyNodeId(), NumberOfNodes()),
      f(n, MyNodeId() + 1, NumberOfNodes()));
}

int main() {
  // Local computation
  ll nl, nr;
  tie(nl, nr) = divide(GetN());

  // Total and left max
  {
    ll s = 0, sl = 0, sr = 0, sans = 0;
    for (ll i = nl; i < nr; ++i) {
      ll x = -GetTaste(i);;
      s += x;
      sl = max(sl, s);
      sr = max(sr + x, 0LL);
      sans = max(sans, sr);
    }

    // Send it, and compute!
    PutLL(0, s);
    PutLL(0, sl);
    PutLL(0, sr);
    PutLL(0, sans);
    // printf("[%lld, %lld): %lld %lld %lld %lld\n", nl, nr, s, sl, sr, sans);
    Send(0);
  }

  // DP
  if (MyNodeId() == 0) {
    ll ans = 0, dp = 0, total = 0;
    for (int i = 0; i < NumberOfNodes(); ++i) {
      Receive(i);
      ll ts = GetLL(i);
      ll tsl = GetLL(i);
      ll tsr = GetLL(i);
      ll tsans = GetLL(i);
      ans = max(ans, max(tsans, dp + tsl));
      dp = max(dp + ts, tsr);
      total += ts;
    }
    printf("%lld\n", -(total - ans));
  }
  return 0;
}