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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include "message.h"
#include "kanapka.h"

#include <iostream>

using namespace std;

int tot_nodes;
int my_node;
int N;

long long min_my(long long x, long long y) {
	if (x <= y)
		return x;
	else
		return y;
}

/*
long long max_my(long long x, long long y) {
	if (x > y)
		return x;
	else
		return y;
}

long long encode_result(int start_or_fin, int node_idx, int is_all_positive)
{
	return (((long long)(start_or_fin ? 1 : 0)) << 32)
		| (((long long)node_idx) << 16)
		| (is_all_positive ? 1 : 0);
}

void decode_result(long long code, int &start_or_fin, int &node_idx, int &is_all_positive)
{
	start_or_fin = (int)(code >> 32);
	node_idx = ((int)(code >> 16) & 0xFFFF);
	is_all_positive = (int)(code & 0xFFFF);
}
*/

/*
void start_to_fin(int start, int after_fin) {
	long long max_since_start = 0;
	long long sum_since_start = 0;
	int min_pos_where_max_gained = start-1;
	for (int i = start; i < after_fin; i++) {
		sum_since_start += GetTaste(i);
		if (sum_since_start > max_since_start) {
			max_since_start = sum_since_start;
			min_pos_where_max_gained = i;
		}
	}
	PutLL(0, sum_since_start);
	PutLL(0, max_since_start);
	PutInt(0, min_pos_where_max_gained);
	Send(0);
}

void fin_to_start(int before_start, int fin) {
	long long max_till_finish = 0;
	long long sum_till_finish = 0;
	int max_pos_where_max_gained = fin + 1;
	for (int i = fin; i > before_start; i--) {
		sum_till_finish += GetTaste(i);
		if (sum_till_finish > max_till_finish) {
			max_till_finish = sum_till_finish;
			max_pos_where_max_gained = i;
		}
	}
	PutLL(1, sum_till_finish);
	PutLL(1, max_till_finish);
	PutInt(1, max_pos_where_max_gained);
	Send(1);
}

int main(int argc, char* argv[])
{
	tot_nodes = NumberOfNodes();
	my_node = MyNodeId();
	N = (int)GetN();
	// BEGIN by ALL nodes, INCLUDING 0 and 1
	int start_idx = (N * my_node) / (tot_nodes);
	int after_fin_idx = (N * (my_node + 1)) / (tot_nodes);
	static char buff[0x40];
	sprintf(buff, "node %d has range [ %d , %d )\n", my_node, start_idx, after_fin_idx);
	cerr << buff << endl;
	if (my_node <= tot_nodes / 2) {
		start_to_fin(start_idx, after_fin_idx);
		fin_to_start(start_idx-1, after_fin_idx-1);
	}
	else {
		fin_to_start(start_idx - 1, after_fin_idx - 1);
		start_to_fin(start_idx, after_fin_idx);
	}

	long long res_since_start = 0LL;
	// END by ALL nodes, INCLUDING 0 and 1
	if (my_node <= 1) { // 0 or 1
		bool failed_while_reaching_end = false;
		long long sum_since_start_global = 0;
		long long max_since_start_global = 0;
		int min_pos_where_max_gained_global = (my_node == 0 ? -1 : N);
		int init_nod = (my_node == 0 ? 0 : tot_nodes - 1);
		int after_end_nod = (my_node == 0 ? tot_nodes : - 1);
		int nod_delta = (my_node == 0 ? +1 : -1);
		int nod_where_breaked = after_end_nod;
		for (int nod = init_nod; nod != after_end_nod; nod+=nod_delta) {
			Receive(nod);
			long long sum_since_start_fragment = GetLL(nod);
			long long max_since_start_fragment = GetLL(nod);
			int min_pos_where_max_gained_fragment = GetInt(nod);
			cerr << "my_node = " << my_node << " received from node " << nod << " ``" << sum_since_start_fragment << " " << max_since_start_fragment << " " << min_pos_where_max_gained_fragment << "''\n";
			long long new_maybemax_since_start_global = sum_since_start_global + max_since_start_fragment;
			if (new_maybemax_since_start_global > max_since_start_global) {
				max_since_start_global = new_maybemax_since_start_global;
				min_pos_where_max_gained_global = min_pos_where_max_gained_fragment;
				cerr << "my_node = " << my_node << " just have changed max_since_start_global to " << max_since_start_global << " ,  min_pos_where_max_gained_global to " << min_pos_where_max_gained_global << "\n";
			}
			sum_since_start_global += sum_since_start_fragment;
		}
		cerr << "my_node = " << my_node << " has nod_where_breaked =  " << nod_where_breaked << "''\n";
		if (my_node == 0) {
			if (max_since_start_global == sum_since_start_global) {
				cout << max_since_start_global << endl;
				cout.flush();
			}
			else {
				Receive(1);
				long long max_from_right_global = GetLL(1);
				cerr << "my_node = " << my_node << " received from node 1 max_from_right_global = " << max_from_right_global << "\n";
				cout << max_since_start_global + max_from_right_global << endl;
				cout.flush();
			}
		}
		else { // my_node == 1
			PutLL(0, max_since_start_global);
			Send(0);
		}
	}
	return 0;
}
*/



int main(int argc, char* argv[])
{
	tot_nodes = NumberOfNodes();
	my_node = MyNodeId();
	N = (int)GetN();
	// BEGIN by ALL nodes, INCLUDING 0
	int start_idx = (N * my_node) / (tot_nodes);
	int after_fin_idx = (N * (my_node + 1)) / (tot_nodes);
	static char buff[0x40];
	sprintf(buff, "node %d has range [ %d , %d )\n", my_node, start_idx, after_fin_idx);
	cerr << buff << endl;

	long long min_sum[2][2] = { { 0LL, 0LL }, { 0LL, 0LL } };
	// [do start exactly at start][do finish exactly at finish]
	for (int idx = start_idx; idx < after_fin_idx; idx++) {
		int curr = GetTaste(idx);
		min_sum[1][1] += curr;
		min_sum[1][0] = min_my(min_sum[1][0], min_sum[1][1]);
		min_sum[0][1] = min_my(min_sum[0][1], 0LL) + curr;
		min_sum[0][0] = min_my(min_sum[0][0], min_sum[0][1]);
//		static char buff[0x40];
//		sprintf(buff, "just calculated for idx = %d ``%lld %lld %lld %lld''\n", idx, min_sum[0][0], min_sum[0][1], min_sum[1][0], min_sum[1][1]);
//		cerr << buff << endl;

////////
//		sum_total += curr;
//		min_among_since_start_only
//		sum_since_last_positive = min_my(0LL, sum_since_last_positive + curr);
//		min_global = min_my(min_global, sum_since_last_positive);
////////
//		min_sum[0][0] = min_my();
//		min_sum[1][0] = min_my(min_sum[1][0], min_sum[1][1] + curr);
//		min_sum[1][1] += curr;
	}
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			PutLL(0, min_sum[i][j]);
	Send(0);
	// END by ALL nodes, INCLUDING 0
	
	if (my_node == 0) {
		long long just_sum_all = 0LL;
		long long sum_till_now = 0;
		long long best_min = 0;

		for (int nod = 0; nod < tot_nodes;  nod++) {
			Receive(nod);
			long long min_sum[2][2] = { { 0LL, 0LL }, { 0LL, 0LL } };
			// [do start exactly at start][do finish exactly at finish]
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 2; j++)
					min_sum[i][j] = GetLL(nod);

			cerr << "my_node = " << my_node << " received from node " << nod << " `` ";
			for (int i = 0; i < 2; i++)
				for (int j = 0; j < 2; j++)
					cerr << min_sum[i][j] << " ";
			cerr << "''\n";

			just_sum_all += min_sum[1][1];
			long long min_for_curr_range = min_my(min_sum[0][0], sum_till_now + min_sum[1][0]);
			if (min_for_curr_range < best_min) {
				best_min = min_for_curr_range;
				cerr << "best_min changed to " << best_min << "\n";
			}
			sum_till_now = min_my(sum_till_now + min_sum[1][1], min_sum[0][1]);
		}
		cerr << "MAIN ANSWER: " << just_sum_all - best_min << endl;
		cout << just_sum_all - best_min << endl;
	}
	return 0;
}