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

#include <iostream>
#include <algorithm>

int main() {

	int nodesC = NumberOfNodes();
	int nodeID = MyNodeId();

	long long N = GetN();

	long long beg = int(double(nodeID) / nodesC*N);
	long long end = int(double(nodeID + 1) / nodesC*N);

	long long* maxRightDirArray = new long long[end - beg];

	long long maxRightDir = 0;
	long long maxLeftDir = 0;
	long long max = 0;

	long long actualSum;
	actualSum = 0;

	//idziemy w prawą stronę
	for (long long i = beg; i < end; ++i){
		actualSum += GetTaste(i);
		maxRightDir = std::max(actualSum, maxRightDir);
		maxRightDirArray[i - beg] = maxRightDir;
	}

	actualSum = 0;
	max = maxRightDir;

	//teraz w lewą
	for (long long i = end - 1; i > beg; --i){
		actualSum += GetTaste(i);
		maxLeftDir = std::max(actualSum, maxLeftDir);
		max = std::max(max, maxLeftDir + maxRightDirArray[i - 1]);
	}
	if (end > beg) actualSum += GetTaste(beg);
	maxLeftDir = std::max(actualSum, maxLeftDir);
	max = std::max(max, maxLeftDir);

	if (nodeID != 0){
		PutLL(0, maxRightDir);
		PutLL(0, maxLeftDir);
		PutLL(0, max);
		PutLL(0, actualSum);
		Send(0);
	} else {

		long long* maxRightDirAll = new long long[nodesC];
		long long* maxLeftDirAll = new long long[nodesC];
		long long* maxAll = new long long[nodesC];
		long long* sumAll = new long long[nodesC];
		long long* sumRightDir = new long long[nodesC];

		maxRightDirAll[0] = maxRightDir;
		maxLeftDirAll[0] = maxLeftDir;
		maxAll[0] = max;
		sumAll[0] = actualSum;

		for (int i = 1; i < nodesC; ++i){
			Receive(i);
			maxRightDirAll[i] = GetLL(i);
			maxLeftDirAll[i] = GetLL(i);
			maxAll[i] = GetLL(i);
			sumAll[i] = GetLL(i);
		}

		actualSum = sumAll[0];
		sumRightDir[0] = actualSum;

		for (int i = 1; i < nodesC; ++i){
			maxRightDirAll[i] = std::max(maxRightDirAll[i - 1], actualSum + maxRightDirAll[i]);
			actualSum += sumAll[i];
			sumRightDir[i] = actualSum;
		}

		//sprawdzamy wartosc przy zjedzeniu calej kanapki
		long long int bestResult = actualSum;

		actualSum = 0;

		for (int i = nodesC - 1; i > 0; --i){
			//jemy calosc z wylaczeniem pewnej czesci znajdujacej sie w tym kawalku
			bestResult = std::max(bestResult, actualSum + maxAll[i] + sumRightDir[i - 1]);
			//jemy najlepsza czesc lewej strony tego kawalka, a z prawej strony nie
			//ruszajac tego kawalka
			bestResult = std::max(bestResult, actualSum + maxLeftDirAll[i] + maxRightDirAll[i - 1]);
			actualSum += sumAll[i];
		}
		bestResult = std::max(bestResult, actualSum + maxAll[0]);
		bestResult = std::max(bestResult, actualSum + maxLeftDirAll[0]);

		std::cout << bestResult << std::endl;

	}


	return 0;

}