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 <array>
#include <vector>
#include <cmath>
#include<algorithm>
#include <iostream>

enum : size_t {
  begin = 0, end = 1, entire = 2, uppermost = 3
 };

typedef long long taste_numeral;
typedef long long taste;
typedef std::array<taste, 4> block;

inline bool cmp(const block& a, const block& b) {
  return a[uppermost] < b[uppermost];
 }

block local_solve(const taste_numeral p, const taste_numeral q) { //[p;q)
  block local_result{{0, 0, 0, 0}};
  taste begin_sum = 0, worst_sum = 0;
  for(auto i = p; i < q; ++i) {
    const taste actual = GetTaste(i);
    begin_sum += actual;
    worst_sum += actual;
    worst_sum = std::min(0LL, worst_sum);
    local_result[begin] = std::min(local_result[begin], begin_sum);
    local_result[uppermost] = std::min(local_result[uppermost], worst_sum);
   }
  local_result[entire] = begin_sum;
  taste& end_sum = begin_sum;
  end_sum = 0;
  for(auto i = q - 1; i >= p; --i) {
    end_sum += GetTaste(i);
    local_result[end] = std::min(local_result[end], end_sum);
   }
  return local_result;
 }

int main() {
  const int nodes_number = NumberOfNodes(), myid = MyNodeId();
  const taste_numeral data_size = GetN();
  if(data_size < 500000) {
    if(myid != 0) {
      return 0;
     }
    const block local_result = local_solve(0, data_size);
    std::cout << local_result[entire] - local_result[uppermost]; 
    return 0;
   }
  const taste_numeral interval = data_size/nodes_number;
  const taste_numeral p = myid * interval;
  const taste_numeral q = (nodes_number == myid + 1) ? data_size : (myid+1) * interval;
  const block local_result = local_solve(p, q);
  if(myid != 0) {
    for(const auto x : local_result) {
      PutLL(0, x);
     }
    Send(0);
    return 0;
   }
  std::vector<block> results(nodes_number);
  results[0] = std::move(local_result);
  for(int i = 1; i < nodes_number; ++i) {
    const int source = Receive(-1);
    for(auto& x : results[source]) {
      x = GetLL(source);
     }
   }
  taste worst_answer = (*std::min_element(std::begin(results), std::end(results), cmp))[uppermost];
  for(auto it = std::begin(results); it != std::end(results); ++it) {
    taste temp = (*it)[end];
    for(auto it2 = it+1; it2 != std::end(results); ++it2) {
      worst_answer = std::min(worst_answer, temp + (*it2)[begin]);
      temp += (*it2)[entire];
     }
   }
  taste whole_sum = 0;
  for(const auto& x : results) {
    whole_sum += x[entire];
   }
  std::cout << whole_sum - worst_answer << '\n';
 }