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

int NUM_NODES;
int NODE;

template<class T>
void Put(int target, const T &value) {
  for (size_t i = 0; i < sizeof(T); ++i) {
    PutChar(target, reinterpret_cast<const char*>(&value)[i]);
  }
}

template<class T>
void Send(int target, const T &value) {
  Put(target, value);
  Send(target);
}

template<class T>
void Get(int source, T &value) {
  for (size_t i = 0; i < sizeof(T); ++i) {
    reinterpret_cast<char*>(&value)[i] = GetChar(source);
  }
}

template<class T>
int Receive(int source, T &value) {
  source = Receive(source);
  Get(source, value);
  return source;
}

// ---------------

struct Data {
  long long sum;
  long long left;
  long long right;
  long long both;
};

inline Data Singleton(long long x) {
  Data data;
  data.sum = x;
  data.left = max(x, 0LL);
  data.right = data.left;
  data.both = data.left;
  return data;
}

Data Combine(const Data &a, const Data &b) {
  Data data;
  data.sum = a.sum + b.sum;
  data.left = max(a.left, a.sum + b.left);
  data.right = max(b.right, b.sum + a.right);
  data.both = max(max(a.both + b.sum,
                      b.both + a.sum),
                  a.left + b.right);
  return data;
}

Data Interval(long long a, long long b) {
  Data data = Singleton(GetTaste(a));
  for (long long i = a+1; i < b; ++i) {
    data = Combine(data, Singleton(GetTaste(i)));
  }
  return data;
}

int main() {
  int NUM_NODES = NumberOfNodes();
  int NODE = MyNodeId();
  long long N = GetN();
  if (NUM_NODES > N) NUM_NODES = N;
  if (NODE >= NUM_NODES) return 0;

  Data data = Interval(NODE * N / NUM_NODES,
                       (NODE+1) * N / NUM_NODES);
  if (NODE > 0) {
    Send(0, data);
  } else {
    for (int i=1;i<NUM_NODES;++i) {
      Data data2;
      Receive(i, data2);
      data = Combine(data, data2);
    }
    cout << data.both << "\n";
  }
}