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

#include <algorithm>
#include <cstdio>
#include <assert.h>
#define REP(x,n) for(int x=0;x<(n);++x)
using namespace std;

#ifdef KAJAK

static int n;
static int* data;

/*static void Init() {
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  assert(1 == scanf("%d", &n));
  data = (int*)malloc((n + 1) * sizeof(int));
  assert(data != NULL);
  for (i = 1; i <= n; ++i) {
    assert(1 == scanf("%d", data + i));
  }
  initialized = 1;
}*/
#define RAND ((rand()<<15)+rand()+(rand()&1 ? (1<<30) : 0))
static void Init() {
  static int initialized = 0;
  if (initialized)
    return;
	n=1000000;
	srand(19960306);
	data = new int[n];
	for(int x=0;x<n;++x) {
		data[x] = RAND%2000000000-1000000000;
	}
  initialized = 1;
}

int Size() {
  Init();
  return n;
}

int ElementAt(int i) {
  Init();
  assert(1 <= i && i <= n);
  return data[i];
}

#endif


int main() {
	int n = Size();
	int ilek = NumberOfNodes();
	int nid = MyNodeId();
  if (n < 2) {
		if (nid==0)
			printf("%d\n",max(0, ElementAt(1)));
    return 0;
  }
  int start = n*nid/ilek;
  int stop = n*(nid+1)/ilek;

  long long current=0, current2=0, elem;
  long long tabl[4] = {0,0,0,0};
  bool ciagl=true;
  for(int i=start;i<stop;++i) {
		tabl[3] += (elem=ElementAt(i+1));
  	current = max(current+elem, 0LL);
  	current2 += elem;
  	tabl[0] = max(tabl[0], current2);
  	tabl[1] = max(tabl[1], current);
		tabl[2] = current;
  }
  if (nid!=0) {
  	PutLL(0, tabl[0]);
  	PutLL(0, tabl[1]);
  	PutLL(0, tabl[2]);
  	PutLL(0, tabl[3]);
		Send(0);
  } else {
  	long long tab[ilek][4];
  	tab[0][0] = tabl[0];
  	tab[0][1] = tabl[1];
  	tab[0][2] = tabl[2];
  	tab[0][3] = tabl[3];
  	REP(x,ilek-1) {
  		int source = Receive(-1);
  		tab[source][0] = GetLL(source);
  		tab[source][1] = GetLL(source);
  		tab[source][2] = GetLL(source);
  		tab[source][3] = GetLL(source);
  	}
  	long long maks = 0, current = 0;
  	REP(x,ilek) { /// tab[x..y]
			maks = max(maks, tab[x][1]);
			current = tab[x][2];
			for(int y=x+1;y<ilek;++y) {
				current += tab[y][0];
				maks = max(maks, current);
				current += tab[y][3]-tab[y][0];
			}
  	}
		printf("%lld\n", maks);
  }
  return 0;
}