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

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

struct stats {
  long long sum;  // whole interval
  long long min;  // prefix
  long long max;  // prefix
  long long opt;  // min subinterval of the whole interval

  stats() : sum(0), min(0), max(0), opt(0) {}
};

/*
long long test(int k) {
  vector<stats> local;
  int N = GetN();
  if (k > 1 && N < 200) {
    return test(1);
  }
  return combine(local);
}

void test() {
  cout << test(1) << endl;
  cout << test(10) << endl;
  cout << test(33) << endl;
  cout << test(100) << endl;
}
*/

stats get_stats(unsigned start, unsigned end) {
  stats local;
  for (unsigned i = start; i < end; ++i) {
    local.sum += GetTaste(i);
    if (local.sum > local.max) 
      local.max = local.sum;
    if (local.sum < local.min) 
      local.min = local.sum;
    if (local.sum - local.max < local.opt)
      local.opt = local.sum - local.max;
  }
  return local;
}

long long combine(const vector<stats> &local) {
  stats global;
  for (auto s : local) {
    if (global.opt > s.opt) {
      global.opt = s.opt;
    }
    if (global.opt > (global.sum - global.max) + s.min) {
      global.opt = (global.sum - global.max) + s.min;
    }
    if (global.sum + s.max > global.max) {
      global.max = global.sum + s.max;
    }
    if (global.sum + s.min < global.min) {
      global.min = global.sum + s.min;
    }
    global.sum += s.sum;
  }

  return global.sum - global.opt;
}

int main() {
  int n = GetN();
  int id = MyNodeId();
  int M = NumberOfNodes();

  if (n < 200 && id > 0) 
    return 0;
  if (n < 200)
    M = 1;

  stats s;
  int portion = n/M;
  if (id < M-1)
    s = get_stats(id*portion, (id+1)*portion);
  else 
    s = get_stats(id*portion, n);
  
  if (id == 0) {
    vector<stats> all;
    all.push_back(s);
    for (int i = 1; i < M; ++i) {
      stats t;
      Receive(i);
      t.sum = GetLL(i);
      t.max = GetLL(i);
      t.min = GetLL(i);
      t.opt = GetLL(i);
      all.push_back(t);
    }
    cout << combine(all) << endl;
  }
  else {
    PutLL(0, s.sum);
    PutLL(0, s.max);
    PutLL(0, s.min);
    PutLL(0, s.opt);
    Send(0);
  }

  return 0;
}