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

#include<bits/stdc++.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))
#define AIN(A, B, C) assert(IN(A, B, C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII> VP;

//typedef int LL;
typedef long long int LL;

struct T {
  LL sum, int_min, pre_min, suf_min;
};

T calc(int start, int end) {
  LL sum = 0, int_min = 0, pre_min = 0, pre_max = 0;
  LL run_min = 0;
  for (int i = start; i <= end; i++) {
    LL num = GetTaste(i);
    sum += num;
    if (pre_min > sum) pre_min = sum;
    if (pre_max < sum) pre_max = sum;

    run_min += num;
    if (run_min > 0) run_min = 0;
    int_min = MIN(int_min, run_min);
  }
  T ret;
  ret.sum = sum;
  ret.int_min = int_min;
  ret.pre_min = pre_min;
  ret.suf_min = sum - pre_max;
  return ret;
}

int my_id;
int n;

T res[200];
int main() {
int xx = NumberOfNodes();
  my_id = MyNodeId();
  n = GetN();
//if(my_id >=10) {cout<<-1; return 0;}
//  if (my_id) return 0;
//  {
//  T res = calc(0, n - 1);
//  cout << res.sum << " " << res.int_min << " " << res.pre_min << " " << res.suf_min << endl;
//  return 0;
//  }
  int start = MAX(1, (n + xx-1) / xx) * my_id;
  int end = MAX(1, (n + xx-1)/xx) * (my_id + 1) - 1;
  end = MIN(end, n - 1);
  long long N = GetN();
  {
    T res = calc(start, end);
    PutLL(0, res.sum);
    PutLL(0, res.int_min);
    PutLL(0, res.pre_min);
    PutLL(0, res.suf_min);
    Send(0);
  }

  if (my_id) return 0;

  for (int i = 0; i < xx; i++) {
    Receive(i);
    res[i].sum = GetLL(i);
    res[i].int_min = GetLL(i);
    res[i].pre_min = GetLL(i);
    res[i].suf_min = GetLL(i);
  }

  LL sum = 0, int_min = 0;
  for (int i = 0; i < xx; i++) {
    sum += res[i].sum;
    int_min = MIN(int_min, res[i].int_min);
  }

  for (int i = 0; i < xx; i++) {
    for (int j = i + 1; j < xx; j++) {
      LL now = res[i].suf_min + res[j].pre_min;
      for (int k = i + 1; k < j; k++) {
        now += res[k].sum;
      }
      int_min = MIN(int_min, now);
    }
  }

  cout << sum - int_min << endl;
  return 0;
}