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
130
#include "maklib.h"
#include "message.h"
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <assert.h>

using namespace std;

typedef long long LL;

#define FOR(x,b,e) for(int x=b; x<=(e); ++x)
#define REP(x,n) for(int x=0; x<(n); ++x)
#define FORD(x,b,e) for(int x=b; x>=(e); --x)

void solve(int *A, int n, LL& best, LL& bestPrefix, LL& bestSuffix, LL& sum){
  REP(x,n){ sum += A[x]; bestPrefix = max(bestPrefix,sum);}
  LL m = 0,minSuff=0;
  if(n>0){
    bestSuffix = max(m,(LL)A[n-1]);
    minSuff=min(m,(LL)A[n-1]);
    m+=A[n-1];
    best = max(best,m-minSuff);
  }
  FORD(x,n-2,0){
    m+=A[x];
    minSuff = min(m,minSuff);
    bestSuffix=max(m,bestSuffix);
    best = max(best,m-minSuff);
  }
}
void test(){
  int t[] = {1,-2,3,-3,5,-2,5,4};
  LL best = 0;
  LL bestPrefix = 0;
  LL bestSuffix = 0;
  LL sum = 0;

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,0,best,bestPrefix,bestSuffix,sum);
  assert(best==0); assert(bestPrefix==0); assert(bestSuffix==0); assert(sum==0);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,1,best,bestPrefix,bestSuffix,sum);
  assert(best==1); assert(bestPrefix==1); assert(bestSuffix==1); assert(sum==1);
 
  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,2,best,bestPrefix,bestSuffix,sum);
  assert(best==1); assert(bestPrefix==1); assert(bestSuffix==0); assert(sum==-1);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,3,best,bestPrefix,bestSuffix,sum);
  assert(best==3); assert(bestPrefix==2); assert(bestSuffix==3); assert(sum==2);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,4,best,bestPrefix,bestSuffix,sum);
  assert(best==3); assert(bestPrefix==2); assert(bestSuffix==0); assert(sum==-1);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,5,best,bestPrefix,bestSuffix,sum);
  assert(best==5); assert(bestPrefix==4); assert(bestSuffix==5); assert(sum==4);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,6,best,bestPrefix,bestSuffix,sum);
  assert(best==5); assert(bestPrefix==4); assert(bestSuffix==3); assert(sum==2);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,7,best,bestPrefix,bestSuffix,sum);
  assert(best==8); assert(bestPrefix==7); assert(bestSuffix==8); assert(sum==7);

  best = bestPrefix = bestSuffix = sum = 0;
  solve(t,8,best,bestPrefix,bestSuffix,sum);
  assert(best==12); assert(bestPrefix==11); assert(bestSuffix==12); assert(sum==11);

}
int main() {
  //test();
  int s = Size();
  int id = MyNodeId();
  int nodes = NumberOfNodes();
  int chunk = s%nodes ? (s+nodes)/nodes : s/nodes;
  int begin = id * chunk, end = min((id+1)*chunk,s);
  int length = end - begin;
  int * t;
  if(length>0){
    t = new int[length];
  }
  REP(x,length) t[x] = ElementAt(x+begin+1);
/*
  printf("Proc: %d %d %d\n",id,begin,end);
  REP(x,length) printf("%d, ",t[x]);
  printf("\n");
 */
  LL sum = 0, bestPrefix = 0, best = 0, bestSuffix = 0;
  solve(t,length,best,bestPrefix,bestSuffix,sum); 
  //printf("%lld\n",best); 
  if(id == 0){
    LL *suffs = new LL[nodes];
    LL *prefs = new LL[nodes];
    LL *sums = new LL[nodes];
    suffs[0] = bestSuffix;
    prefs[0] = bestPrefix;
    sums[0] = sum;  
    FOR(x,1,nodes-1){
      Receive(x);
      best = max(best,GetLL(x));
      suffs[x] = GetLL(x);
      prefs[x] = GetLL(x);
      sums[x] = GetLL(x);
    }
    LL ss = 0;
    FOR(x,0,nodes-1){
      ss = 0;
      FOR(y,x+1,nodes-1){
        best = max(best,suffs[x]+ss+prefs[y]);
        ss+=sums[y];
      }
    }
    printf("%lld\n",best);
  } else {
    PutLL(0,best);
    PutLL(0,bestSuffix);
    PutLL(0,bestPrefix);
    PutLL(0,sum);
    Send(0);
  }


  return 0;
}