Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
  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
#include "kanapka.h"
#include "message.h"
#include <bits/stdc++.h>
using namespace std;

pair<int, int> getStartEnd(int n, int nodeID, int totalNodes){
	// oblicz pocz�tek i koniec.
	int nodesPerInstance = ceil((double)n / (double)totalNodes);
	int start = nodeID * nodesPerInstance;
	int end = start + nodesPerInstance - 1;
	if(end >= n){
		end = n - 1;
	}
	return pair<int, int>(start, end);
}

int main(){
	int n = GetN();
	int myNode = MyNodeId();
	int totalNodes = NumberOfNodes();
	pair<int, int> startEnd = getStartEnd(n, myNode, totalNodes);
	int start = startEnd.first;
	int end = startEnd.second;
	
	long long sum = 0;
	long long max_prefix = 0;
	long long min_prefix = 0;
	long long max_suffix;
	long long max_infix = 0;	
	long long current_infix = 0;
	
	for(int i = start; i <= end; ++i){
		// odwracam liczby na ujemne, obliczam najnizsze mozliwe podslowo
		long long value = - GetTaste(i);
		sum += value;
		current_infix += value;
		if(sum > max_prefix){
			max_prefix = sum;
		}
		if(sum < min_prefix){
			min_prefix = sum;
		}
		if(current_infix < 0){
			current_infix = 0;
		}
		if(current_infix > max_infix){
			max_infix = current_infix;
		}
	}
	max_suffix = sum - min_prefix;
	
	if(myNode > 0){
		PutLL(0, sum);
		PutLL(0, max_prefix);
		PutLL(0, max_suffix);
		PutLL(0, max_infix);
		Send(0);
	}else{
		long long totalSum = sum;
		long long bestResult = max_infix;
		long long values[totalNodes][3];
		values[0][0] = sum;
		values[0][1] = max_prefix;
		values[0][2] = max_suffix;
		
		for(int i = 1; i < totalNodes; ++i){
			int idx = Receive(-1);
			for(int j = 0; j < 3; ++j){
				values[idx][j] = GetLL(idx);
			}
			long long infixV = GetLL(idx);
			
			if(infixV > bestResult){
				bestResult = infixV;
			}
			totalSum += values[idx][0];
		}
		
		long long left[totalNodes];
		long long right[totalNodes];
		
		left[0] = values[0][2];
		for(int i = 1; i < totalNodes; ++i){
			left[i] = max(left[i - 1] + values[i][0], values[i][2]);
		}
		
		right[totalNodes - 1] = values[totalNodes - 1][1];
		for(int i = totalNodes - 2; i >= 0; --i){
			right[i] = max(right[i + 1] + values[i][0], values[i][1]);
		}
		
		for(int i = 1; i < totalNodes; ++i){
			// liczymy pare (i-1, i)
			long long result = left[i - 1] + right[i];
			if(result > bestResult){
				bestResult = result;
			}
		}
		
		bestResult = -(totalSum - bestResult);
		cout << bestResult << endl;
	}
	return 0;
}