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

#include "message.h"
#include "kanapka.h"

namespace {
  struct Result {
    long long total;
    long long worst;
    long long worst_pref;
    long long worst_suf;
  };

  void send(int target, Result const& res)
  {
    PutLL(target, res.total);
    PutLL(target, res.worst);
    PutLL(target, res.worst_pref);
    PutLL(target, res.worst_suf);
    Send(target);
  }

  pair<int, Result> receive(int source=-1)
  {
    source = Receive(source);
    Result res;
    res.total = GetLL(source);
    res.worst = GetLL(source);
    res.worst_pref = GetLL(source);
    res.worst_suf = GetLL(source);
    return {source, move(res)};
  }

  Result calculate(int l, int r)
  {
    Result res{0, 0, 0, 0};
    long long cur = 0;
    long long cur_pref = 0;
    long long cur_suf = 0;
    for (int i = l; i < r; ++i) {
      int x = GetTaste(i);
      int y = GetTaste(r-1-i+l);
      cur = min(0LL, cur + x);
      cur_pref += x;
      cur_suf += y;
      res.total += x;
      res.worst = min(res.worst, cur);
      res.worst_pref = min(res.worst_pref, cur_pref);
      res.worst_suf = min(res.worst_suf, cur_suf);
    }
    return res;
  }

  long long combine(vector<Result> const& results)
  {
    long long total = 0;
    long long cur = 0;
    long long worst = 0;
    for (auto const& r: results) {
      worst = min(worst, r.worst);
      worst = min(worst, cur + r.worst_pref);
      cur = min(r.worst_suf, cur + r.total);
      total += r.total;
    }
    return total - worst;
  }
}

int main()
{
  int n = GetN();
  int k = min(NumberOfNodes(), n);
  int id = MyNodeId();
  if (id >= k) return 0;

  int l = (id + 0LL) * n / k;
  int r = (id + 1LL) * n / k;
  Result result = calculate(l, r);
  if (id > 0) {
    send(0, move(result));
  } else {
    vector<Result> results;
    results.reserve(k);
    results.push_back(move(result));
    for (int i = 1; i < k; ++i) {
      results.push_back(move(receive(i).second));
    }
    cout << combine(move(results)) << '\n';
  }

  return 0;
}