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

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
using namespace std;

using ll = long long;

//int NumberOfNodes()
//{
//	return 1;
//}
//
//int MyNodeId()
//{
//	return 0;
//}
//long long GetLL(int source)
//{
//	return 0;
//}
//void PutLL(int target, long long value)
//{
//}

struct result
{
	ll total_sum;
	ll worst_sum;
	ll worst_preffix;
	ll worst_suffix;
};

int main()
{

	long long N = GetN();
	long long nodes = NumberOfNodes();
	long long first = (MyNodeId() * N) / NumberOfNodes();
	long long last = ((MyNodeId() + 1) * N) / NumberOfNodes();
	long long length = last - first;
	
	{
		ll total = 0;
		ll worst = 0;
		ll tmp = 0;
		ll preffix = 0;
		ll best_preffix = 0;
		for (ll i = first; i < last; ++i) {
			ll t = GetTaste(i);
			total += t;
			preffix = std::min(preffix, total);
			best_preffix = std::max(best_preffix, total);
			tmp = std::min(tmp + t, 0LL);
			worst = std::min(worst, tmp);
		}

		ll suffix = total - best_preffix;
		ll result = total - worst;

		PutLL(0, total);
		PutLL(0, worst);
		PutLL(0, preffix);
		PutLL(0, suffix);
		Send(0);
	}
	

	int node = MyNodeId();
	if (node == 0)
	{
		result r[1000];
		for (int i = 0; i < nodes; ++i)
		{
			int n = Receive(-1);
			r[n].total_sum = GetLL(n);
			r[n].worst_sum = GetLL(n);
			r[n].worst_preffix = GetLL(n);
			r[n].worst_suffix = GetLL(n);
		}

		ll total = 0;
		ll worst = 0;
		ll worst_preffix = 0;
		for (int i = 0; i < nodes; ++i)
		{
			total += r[i].total_sum;
			worst = std::min(worst, r[i].worst_sum);
			worst = std::min(worst, worst_preffix + r[i].worst_preffix);
			worst_preffix = std::min(worst_preffix + r[i].total_sum, r[i].worst_suffix);
		}

		ll result = total - worst;
		cout << result << endl;
}	
	return 0;
}