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
#include "kanapka.h"
#include "message.h"

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  long long n = GetN();
  int nodes = NumberOfNodes();
  int node = MyNodeId();

  long long block_size = (n + nodes - 1) / nodes;
  long long beg = min(n, block_size * node);
  long long end = min(n, beg + block_size);
  int size = end - beg;

  long long pref = 0, suf = 0, sum = 0, prefsuf = 0;
  long long cur = 0;
  long long taste[size];
  long long best_pref[size];
  for (long long i=beg; i<end; i++) taste[i-beg] = GetTaste(i);

  for (int i=0; i<size; i++) {
    cur += taste[i];
    best_pref[i] = max(cur, (i ? best_pref[i-1] : 0));
  }
  pref = (size ? best_pref[size-1] : 0);
  sum = cur;
  cur = 0;
  for (int i=size-1; i>=0; i--) {
    cur += taste[i];
    prefsuf = max(prefsuf, cur + (i ? best_pref[i-1] : 0));
    suf = max(suf, cur);
  }

  if (node) {
    PutLL(0, sum);
    PutLL(0, pref);
    PutLL(0, suf);
    PutLL(0, prefsuf);
    Send(0);
  } else {
    long long sums[nodes], prefs[nodes], sufs[nodes], prefsufs[nodes];
    sums[0] = sum;
    prefs[0] = pref;
    sufs[0] = suf;
    prefsufs[0] = prefsuf;
    for (int i=1; i<nodes; i++) {
      int x = Receive(-1);
      sums[x] = GetLL(x);
      prefs[x] = GetLL(x);
      sufs[x] = GetLL(x);
      prefsufs[x] = GetLL(x);
    }
    long long res = 0;
    
    long long total = 0;
    for (int i=0; i<nodes; i++) total += sums[i];
    res = max(res, total);
    
    long long best_pref[nodes], cur = 0, prefsum[nodes], sufsum[nodes];
    for (int i=0; i<nodes; i++) prefsum[i] = (i ? prefsum[i-1] : 0) + sums[i];
    for (int i=nodes-1; i>=0; i--) sufsum[i] = total - (i ? prefsum[i-1] : 0);
    for (int i=0; i<nodes; i++) {
      best_pref[i] = max(cur + prefs[i], (i ? best_pref[i-1] : 0));
      cur += sums[i];
    }
    cur = 0;
    for (int i=nodes-1; i>=0; i--) {
      res = max(res, cur + sufs[i] + (i ? best_pref[i-1] : 0));
      cur += sums[i];
    }
    for (int i=0; i<nodes; i++)
      res = max(res, (i ? prefsum[i-1] : 0) + (i < nodes-1 ? sufsum[i+1] : 0) + prefsufs[i]);
    cout << res << "\n";
  }
  
  return 0;
}