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
#include <iostream>
#include <utility>
#include <algorithm>
#include <tuple>

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

struct ConfigContainer {
	int nodes, my_node;
	
	ConfigContainer() {
		nodes = NumberOfNodes();
		my_node = MyNodeId();
	}
} config;

unsigned get_division_point(long long num) {
	return GetN() / config.nodes * num + std::min(num, GetN() % config.nodes);
};

std::pair<unsigned, unsigned> get_indices() {
	long long n = GetN();
	unsigned start = get_division_point(config.my_node);
	unsigned end = get_division_point(config.my_node + 1);

	return {start, end};
}

struct result {
	long long pref, suf, sum, best;
	result(long long pref, long long suf, long long sum, long long best):
		pref(pref), suf(suf), sum(sum), best(best) {}

	result(long long x): pref(std::min(x, 0LL)), suf(std::min(x, 0LL)), sum(x), best(std::min(x, 0LL)) {}

	void send(int instance) {
		PutLL(instance, pref);
		PutLL(instance, suf);
		PutLL(instance, sum);
		PutLL(instance, best);

		Send(instance);
//		std::cerr << "sent: " << pref << " " << suf << " " << sum << " " << best << std::endl;
	}

	static result const receive(int instance) {
		long long pref, suf, sum, best;

		Receive(instance);

		pref = GetLL(instance);
		suf = GetLL(instance);
		sum = GetLL(instance);
		best = GetLL(instance);

		return {pref, suf, sum, best};
	}

	static const result empty;
};

const result result::empty(0);

result const merge (result const& lhs, result const& rhs) {
	return {
		std::min(lhs.pref, lhs.sum + rhs.pref),
		std::min(rhs.suf, rhs.sum + lhs.suf),
		lhs.sum + rhs.sum,
		std::min({lhs.best, rhs.best, lhs.suf+rhs.pref})
	};
}

void first_phase() {
	unsigned first, last;
	long long pref, sum, suf;

	std::tie(first, last) = get_indices();

	result res = result::empty;
	for(; first < last; first++) {
		res = merge(res, GetTaste(first));
	}

	res.send(0);
}

void second_phase() {
	result res = result::receive(0);
	for(int i=1; i<config.nodes; i++) {
		res = merge(res, result::receive(i));
	}

	std::cout << res.sum - res.best << std::endl;
}

int main() {
	first_phase();
	if(config.my_node == 0) second_phase();
}