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

#include <cstdio>
#include <vector>
#include <limits>

using namespace std;
long long max(long long a, long long b) {
  return a >= b ? a : b;
}
long long min(long long a, long long b) {
  return a <= b ? a : b;
}
const int MASTER = 0;
int main() {
  long long N = GetN();
  int num_nodes = NumberOfNodes();
  int node_id = MyNodeId();
  int start = (N * node_id) / num_nodes;
  int end = (N * (node_id + 1)) / num_nodes;

  long long sum = 0, max_prefix_sum = numeric_limits<long long>::min();
  long long min_prefix_sum = numeric_limits<long long>::max();
  int best_suffix_i = end;
  for (int i = start; i < end; ++i) {
    sum += GetTaste(i);
    max_prefix_sum = max(max_prefix_sum, sum);
    if (sum < min_prefix_sum) {
      best_suffix_i = i;
    }
    min_prefix_sum = min(min_prefix_sum, sum);
  }
  long long max_suffix_sum = sum - min_prefix_sum;

  PutLL(MASTER, sum);
  PutLL(MASTER, max_prefix_sum);
  PutLL(MASTER, max_suffix_sum);
  Send(MASTER);

  if (node_id == MASTER) {
    vector<long long> sums(num_nodes), prefix_max(num_nodes), suffix_max(num_nodes);
    for (int i = 0; i < num_nodes; ++i) {
      Receive(i);
      sums[i] = GetLL(i);
      prefix_max[i] = GetLL(i);
      suffix_max[i] = GetLL(i);
    }
    vector<long long> prefix_sums(num_nodes), suffix_sums(num_nodes);
    for (int i = 0; i < num_nodes; ++i) {
      prefix_sums[i] += sums[i];
      if (i > 0) {
	prefix_sums[i] += prefix_sums[i-1];
	prefix_max[i] = max(prefix_sums[i - 1] + prefix_max[i], prefix_max[i - 1]);
      }			    
    }
    for (int i = num_nodes - 1; i >= 0; --i) {
      suffix_sums[i] += sums[i];
      if (i < num_nodes - 1) {
	suffix_sums[i] += suffix_sums[i + 1];
	suffix_max[i] = max(suffix_sums[i + 1] + suffix_max[i], suffix_max[i + 1]);
      }
    }
    for (int i = 0; i < num_nodes; ++i) {
      PutLL(i, i > 0 ? prefix_sums[i-1]:0LL);
      PutLL(i, i>0?prefix_max[i-1]:0LL);
      PutLL(i, i<num_nodes-1?suffix_sums[i+1]:0LL);
      PutLL(i, i<num_nodes-1?suffix_max[i+1]:0LL);
      Send(i);
    }
  }

  Receive(MASTER);
  long long prefix_sum = GetLL(MASTER);
  long long prefix_max = GetLL(MASTER);
  long long suffix_sum = GetLL(MASTER);
  long long suffix_max = GetLL(MASTER);

  long long best_sum = prefix_max + max(suffix_max, suffix_sum + sum);
  long long sum_l = 0, best_l = 0;
  for (int i= start; i < end; ++i) {
    sum_l += GetTaste(i);
    best_l = max(sum_l, best_l);
    long long best_r = i < best_suffix_i ? max_suffix_sum : (sum - sum_l);
    best_sum = max(best_sum, 
		   max(prefix_max, prefix_sum + best_l) + max(suffix_max, suffix_sum + best_r));
  }
  PutLL(MASTER, best_sum);
  Send(MASTER);

  if (node_id == MASTER) {
    long long best_sum = 0;
    for (int i = 0; i < num_nodes; ++i) {
      Receive(i);
      best_sum = max(best_sum, GetLL(i));
    }
    printf("%lld", best_sum);
  }
}