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

typedef long long LL;

const int maxInst = 100;
const int maxN = 5000000+10;
LL sumsL[maxInst], sumsR[maxInst], maxisL[maxInst], maxisR[maxInst];
LL currMaxL[maxN], currMaxR[maxN];

int main() {
  LL N = GetN();
  LL id = MyNodeId();
  LL non = NumberOfNodes();

  LL beg = id*N/non;
  LL end = (id+1)*N/non;

  LL maxiL = 0, maxiR = 0, sumL = 0, sumR = 0;
  for(LL i = beg, j = 1; i < end; ++i, ++j) {
    sumL += GetTaste(i);
    maxiL = max(maxiL, sumL);
    currMaxL[j] = maxiL;
  }
  for(LL i = end-1, j = 1; i >= beg; --i, ++j) {
    sumR += GetTaste(i);
    maxiR = max(maxiR, sumR);
    currMaxR[j] = maxiR;
  }
  PutLL(0, maxiL);
  PutLL(0, maxiR);
  PutLL(0, sumL);
  Send(0);

  if(id == 0) {
    for(int i = 0; i < non; ++i) {
      int k = Receive(-1);
      maxisL[k] = GetLL(k);
      maxisR[k] = GetLL(k);
      sumsL[k] = sumsR[k] = GetLL(k);
    }
    LL csum = 0;
    LL cmax = 0;
    for(int i = 0; i < non; ++i) {
      LL t = sumsL[i];
      sumsL[i] = csum;
      csum += t;
      t = maxisL[i];
      maxisL[i] = cmax;
      cmax = max(t+sumsL[i], cmax);
    }
    csum = 0;
    cmax = 0;
    for(int i = non-1; i >= 0; --i) {
      LL t = sumsR[i];
      sumsR[i] = csum;
      csum += t;
      t = maxisR[i];
      maxisR[i] = cmax;
      cmax = max(t+sumsR[i], cmax);
    }
    for(int i = 0; i < non; ++i) {
      PutLL(i, maxisL[i]);
      PutLL(i, maxisR[i]);
      PutLL(i, sumsL[i]);
      PutLL(i, sumsR[i]);
      Send(i);
    }
  }
  Receive(0);
  maxiL = GetLL(0);
  maxiR = GetLL(0);
  sumL = GetLL(0);
  sumR = GetLL(0);
  LL result = 0;
  for(LL i = beg; i <= end; ++i) {
    LL mxL = max(maxiL, sumL+currMaxL[i-beg]);
    LL mxR = max(maxiR, sumR+currMaxR[end-beg-(i-beg)]);
    result = max(result, mxL+mxR);
  }
  PutLL(0, result);
  Send(0);
  if(id == 0) {
    for(int i = 0; i < non; ++i) {
      int k = Receive(-1);
      result = max(result, GetLL(k));
    }
    std::cout << result << std::endl;
  }
  return 0;
}