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
/*	Arek Wróbel - skater
 *
 *	Zadanie: Maksymalna podtablica
 */
#include "message.h"
#include "maklib.h"

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define REP(I, N) for(int I=0; I<(N); ++I)
#define FOR(I, M, N) for(int I=(M); I<=(N); ++I)
#define FORD(I, M, N) for(int I=(M); I>=(N); --I)
#define FOREACH(IT, CON) for(__typeof(CON.begin()) IT=CON.begin(); IT!=CON.end(); ++IT)
#define ST first
#define ND second
#define MP make_pair
#define PB push_back
const int INF=1000000000;
const LL INFLL=1000000000000000000LL;

int numberOfNodes;
int myNodeId;
int N;

//int usedNodes;
int start, n;

LL sum = 0;
LL minim = 0;

int main()
{
	numberOfNodes = NumberOfNodes();
	myNodeId = MyNodeId();
	N = Size();
	n = (N + numberOfNodes - 1) / numberOfNodes;
	numberOfNodes = (N + n - 1) / n;
	if (myNodeId >= numberOfNodes)
		return 0;
	start = n * myNodeId;
	if (myNodeId == numberOfNodes-1)
		n = N - start;
//	printf("%d: %d %d %d %d\n", myNodeId, N, numberOfNodes, start, n);
	
	REP(i, n) {
		sum += ElementAt(start+i+1);
		minim = min(minim, sum);
	}
	
	LL benchmark;
	if (myNodeId == 0) {
		benchmark = sum;
		for (int i = 1; i < numberOfNodes; ++i) {
			PutLL(i, minim);  // wysyłam mu minimum wszystkich poprzednich
			PutLL(i, benchmark);  // wysyłam mu sumę wszystkich poprzednich
			Send(i);
			
			Receive(i);
			minim = min(minim, GetLL(i)+benchmark);
			benchmark += GetLL(i);  // zmieniam sobie punkt odniesienia na następny
		}
		benchmark = minim = 0;
	} else {
		PutLL(0, minim);
		PutLL(0, sum);
//		printf("%d -> %lld %lld\n", myNodeId, sum[n-1], minim);
		Send(0);
		Receive(0);
		minim = GetLL(0);
		benchmark = GetLL(0);
//		printf("%d <- %lld %lld\n", myNodeId, benchmark, minim);
	}
	
	sum = benchmark;
	LL wy = 0;
	REP(i, n) {
		sum += ElementAt(start+i+1);
		minim = min(minim, sum);
		wy = max(wy, sum-minim);
	}
	
	if (myNodeId == 0) {
		for (int i = 1; i < numberOfNodes; ++i) {
			Receive(i);
			wy = max(wy, GetLL(i));
		}
		printf("%lld\n", wy);
	} else {
		PutLL(0, wy);
		Send(0);
	}
//	delete[] sum;
//	printf("KONIEC!\n");
	return 0;
}