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
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include "kanapka.h"
#include "message.h"
#include <vector>
#include <algorithm>

using ll = long long;


struct data
{
	ll total;
	ll maxfront;
	ll maxend;
	ll maxmid;

	void send(int _target)
	{
		PutLL(_target, total);
		PutLL(_target, maxfront);
		PutLL(_target, maxend);
		PutLL(_target, maxmid);
		Send(_target);
	}

	void receive(int _source)
	{
		int source = Receive(_source);
		total = GetLL(source);
		maxfront = GetLL(source);
		maxend = GetLL(source);
		maxmid = GetLL(source);
	}
};


int main()
{
	const ll limit = 100000ll;

	ll non = NumberOfNodes();
	ll myid = MyNodeId();
	// -----
	ll n = GetN();
	ll step = n / non;
	ll start = step * myid;
	ll end = myid == non - 1 ? n : start + step;
	if (n < limit) {
		if (myid != 0) {
			return 0;
		}
		start = 0; end = n;
	}
	ll len = end - start;
	ll totalend = 0;
	ll totalmix = 0;
	data intel{ 0, 0, 0, 0 };
	
	for (ll i = 0; i < len; ++i) {
		ll taste_i = GetTaste(i + start);
		totalend += GetTaste(end - i - 1);
		intel.total += taste_i;
		totalmix = std::min(totalmix + taste_i, 0ll);
		if (intel.maxfront < intel.total) {
			intel.maxfront = intel.total;
		}
		if (intel.maxend < totalend) {
			intel.maxend = totalend;
		}
		if (intel.maxmid > totalmix) {
			intel.maxmid = totalmix;
		}
	}
	intel.maxmid = intel.total - intel.maxmid;
	
	if (myid != 0) {
		intel.send(0);
	} else {
		if (n < limit) {
			std::cout << intel.maxmid << std::endl;
		} else {
			std::vector<data> comp(non);
			comp[0] = intel;
			for (int i = 1; i < non; ++i) {
				comp[i].receive(i);
			}

			std::vector<ll> sumtotal(non + 1);
			sumtotal[non] = 0;
			for (int i = non - 1; i >= 0; --i) {
				sumtotal[i] = sumtotal[i + 1] + comp[i].total;
			}

			ll total = 0;
			ll bestmid = 0;
			for (int i = 0; i < non; ++i) {
				ll mid = total + comp[i].maxmid + sumtotal[i + 1];
				if (bestmid < mid) {
					bestmid = mid;
				}
				total += comp[i].total;
			}

			std::vector<ll> bestend(non + 1);
			bestend[non] = 0;
			for (int i = non - 1; i >= 0; --i) {
				bestend[i] = std::max(bestend[i + 1], sumtotal[i + 1] + comp[i].maxend);
			}

			total = 0;
			ll bestmix = bestend[0];
			for (int i = 0; i < non; ++i) {
				ll front = total + comp[i].maxfront + bestend[i + 1];
				if (bestmix < front) {
					bestmix = front;
				}
				total += comp[i].total;
			}	

			std::cout << std::max(bestmid, bestmix) << std::endl;
		}
	}
	return 0;
}