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

#include <algorithm>
#include <iostream>

typedef long long LL;

using namespace std;

struct Data {
    LL sum;
    LL best;
    LL bestL;
    LL bestR;
};

Data compute(int x) {
    Data result;
    result.sum = GetTaste(x);
    result.best = min(0ll, result.sum);
    result.bestL = result.bestR = result.best;
    return result;
}

Data collect(Data left, Data right) {
    Data result;
    result.sum = left.sum + right.sum;
    result.best = min(left.best, right.best);
    result.best = min(result.best, left.bestR + right.bestL);
    result.bestL = min(left.bestL, left.sum + right.bestL);
    result.bestR = min(left.bestR + right.sum, right.bestR);
    return result;
}

Data compute(int left, int right) {
    Data result = compute(left);
    for(int i=left+1; i<right; i++) {
        result = collect(result, compute(i));
    }
    return result;
}

void sendData(Data data) {
    PutLL(0, data.sum);
    PutLL(0, data.best);
    PutLL(0, data.bestL);
    PutLL(0, data.bestR);
    Send(0);
}

Data receiveData(int from) {
    Receive(from);
    Data result;
    result.sum = GetLL(from);
    result.best = GetLL(from);
    result.bestL = GetLL(from);
    result.bestR = GetLL(from);
    return result;
}

int main() {
  int N = GetN();
  int nodes = NumberOfNodes();
  nodes = min(nodes, N);
  int me = MyNodeId();

  if(me >= nodes) {
    return 0;
  }

  Data portion = compute(LL(N) * me / nodes, LL(N) * (me+1) / nodes);

  if(me != 0) {
    sendData(portion);
  } else {
      for(int i=1; i<nodes; i++) {
        portion = collect(portion, receiveData(i));
      }
      LL result = portion.sum - portion.best;
      cout << result << "\n";
  }

  return 0;
}