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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "kanapka.h"
#include "message.h"

#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

void show_array(long long ar[], long long n){
  for (int i = 0; i< n; i++){
    cout << ar[i] << ",";
  }
}

int main() {
  //  compute and send all sums

  long long id = MyNodeId();
  long long N = GetN();
  long long nn = NumberOfNodes();
  if (nn > N) {
    nn = N;
  }

  long long batch_size = ceil(1.0 * N / nn);
  long long begin = id * batch_size;
  long long end = min(begin + batch_size, N);
  long long actual_nodes = ceil(1.0 * N / batch_size);

  if (nn >= actual_nodes) nn = actual_nodes;

  if (id >= nn) return 0;

  long long sum = 0;
  long long current_best_left_sum = 0;
  long long *best_left_sum;
  //  LIMITS: memory: 8 * 10^8 = 800MB on 1 node, 8MB on 100 nodes
  best_left_sum = new long long [end-begin];
  for (int i = begin; i < end; i++){
    sum += GetTaste(i);
    if (current_best_left_sum < sum) {
      current_best_left_sum = sum;
    }
    best_left_sum[i-begin] = current_best_left_sum;
  }

  for (int k = 0; k < nn; k++){
    PutLL(k, sum);
    PutLL(k, current_best_left_sum);
    //  LIMITS: messages count: nn*2, size: *8
    Send(k);
  }

  long long sums[nn];
  long long cbls[nn];   //  current best left sum
  for (int k = 0; k < nn; k++){
      Receive(k);
      sums[k] = GetLL(k);
      cbls[k] = GetLL(k);
  }

  //  calculate sum_right, sum_left
  long long sr = 0;
  long long sl = 0;
  for (int i = 0; i < nn; i++){
    if (i>id) sr += sums[i];
    else if (i<id) sl += sums[i];
  }

  //  find max_left_inside_current
  long long mwc = 0;
  long long current_from_right = sr;
  long long best_from_right = 0;
  for (int i = end-1; i>=begin; i--) {
    current_from_right += GetTaste(i);
    if (current_from_right > best_from_right) best_from_right = current_from_right;
    long long best_from_left = 0;
    if (i > begin) {
      best_from_left = best_left_sum[i-begin - 1];
    }
    long long best_here = sl + best_from_left + current_from_right;
    if (best_here > mwc) mwc = best_here;
  }
//  best_from_right += sr;

  //  find max_wo_current
  long long mwoc = 0;
  long long sum_from_left = 0;
  for (int k = 0; k < id; k++){
    long long current = sum_from_left + cbls[k] + best_from_right;
    if (current > mwoc) mwoc = current;
    sum_from_left += sums[k];
  }

  long long this_batch_best = max(mwc, mwoc);

  //  DEBUG
//  if (id >= 0) {
//    for (int i = 0; i < N; i++)
//      cout << GetTaste(i) << ", ";
//    cout << endl;
//    cout << "---id: "; cout << id; cout << endl;
//    cout << begin << ", " << end << endl;
//    cout << " sums: "; show_array(sums, nn); cout << endl;
//    cout << " cbls: "; show_array(cbls, nn); cout << endl;
//    cout << " mwc: "; cout << mwc; cout << endl;
//    cout << " mwoc: "; cout << mwoc; cout << endl;
//    cout << " best_from_right: "; cout << best_from_right; cout << endl;
//    cout << " sl: "; cout << sl; cout << endl;
//    cout << " sr: "; cout << sr; cout << endl;
//  }

  //  send result to 0
  PutLL(0, this_batch_best);
    //  LIMITS: messages count: 1, size: *8
  Send(0);

  if (id == 0){
    long long best_overall = 0;
    for (int k = 0; k < nn; k++){
      Receive(k);
      long long k_best = GetLL(k);
      if (k_best > best_overall) best_overall = k_best;
    }
    cout << best_overall << endl;
  }

  return 0;
}