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 <algorithm>
#include <cstdio>

#include "message.h"
#include "kanapka.h"

namespace
{
	int instanceID;
	int numberOfInstances;

	long long sandwichSegments;
	long long rangeBegin, rangeEnd;

	void configure()
	{
		// Save these variables to avoid further function calls
		instanceID = MyNodeId();
		numberOfInstances = NumberOfNodes();

		// Calculate range
		sandwichSegments = GetN();
		rangeBegin = instanceID * sandwichSegments / numberOfInstances;
		rangeEnd = (instanceID + 1) * sandwichSegments / numberOfInstances;
	}
}

namespace
{
	long long resultSumLeft, resultSumRight, resultSumInner, resultSumTotal;

	void calculate()
	{
		// Calculate the minimum sum on the left side, right side and inside
		long long sumLeft = 0;
		long long minLeft = 0;
		long long minInner = 0;
		long long minCurrent = 0;

		const long long loopEnd = rangeEnd;
		for (long long i = rangeBegin; i < rangeEnd; i++)
		{
			long long val = GetTaste(i);

			sumLeft += val;
			minLeft = std::min(minLeft, sumLeft);

			minCurrent = std::min(minCurrent + val, 0LL);
			minInner = std::min(minInner, minCurrent);
		}

		resultSumLeft = minLeft;
		resultSumRight = minCurrent;
		resultSumInner = minInner;
		resultSumTotal = sumLeft;
	}
}

static void communicate()
{
	if (instanceID != 0)
	{
		// Send data to the zeroth instance
		PutLL(0, resultSumLeft);
		PutLL(0, resultSumRight);
		PutLL(0, resultSumInner);
		PutLL(0, resultSumTotal);
		Send(0);
	}
	else
	{
		// The merging step is simple, and number of concurrent instances
		// is small, so linear merging should suffice
		long long minLeft = resultSumLeft;
		long long minRight = resultSumRight;
		long long minInner = resultSumInner;
		long long total = resultSumTotal;

		long long theirLeft, theirRight, theirInner, theirTotal;

		for (int i = 1; i < numberOfInstances; i++)
		{
			// fprintf(stderr, "MY: %lld %lld %lld %lld\n", minLeft, minRight, minInner, total);

			Receive(i);
			theirLeft = GetLL(i);
			theirRight = GetLL(i);
			theirInner = GetLL(i);
			theirTotal = GetLL(i);

			// fprintf(stderr, "%d: %lld %lld %lld %lld\n", i, theirLeft, theirRight, theirInner, theirTotal);

			minInner = std::min({minInner, theirInner, minRight + theirLeft});
			minLeft = std::min(minLeft, total + theirLeft);
			minRight = std::min(theirRight, minRight + theirTotal);
			total += theirTotal;
		}

		// Print the results
		printf("%lld\n", total - minInner);
	}
}

int main()
{
	configure();
	calculate();
	communicate();

	return 0;
}