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

using namespace std;

long long min( long long a, long long b ) {
	return ( ( a < b ) ? a : b );
}

const int n = (int)GetN();
const int num_of_nodes = NumberOfNodes();
const int my_node_id = MyNodeId();

int get_node_start_pos( int node_num ) {
	return ( n * node_num ) / num_of_nodes;
}

int main() {

	int left_limit = get_node_start_pos( my_node_id );      //left limit of this node's block
	int right_limit = get_node_start_pos( my_node_id + 1 ); //right limit of this node's block
								//which is the left limit of the following node's block
	long long lowest_left = 0, lowest_right = 0, lowest_middle = 0, sum = 0;
	
	for( int i = left_limit; i < right_limit; i++ ) {		
		long long val = GetTaste( i );
		sum += val;
		lowest_right += val;
		if( lowest_right > 0 ) lowest_right = 0;      //the most negative part from the right can be empty
		lowest_middle = min( lowest_middle, lowest_right ); //preserve most negative part completely inside this node's block
	}

	for( int i = right_limit; i-- > left_limit; ) {
		long long val = GetTaste( i );
		lowest_left += val;
		if( lowest_left > 0 ) lowest_left = 0;        //the most negative part from the left can be empty
	}

	PutLL( 0, lowest_right );
	PutLL( 0, lowest_left );
	PutLL( 0, lowest_middle );
	PutLL( 0, sum );
	Send( 0 );

	if( my_node_id != 0 ) return 0;

	long long total_sandwich = 0, best_antisandwich = 0, prev_lowest_part = 0;

	for( int i = 0; i < num_of_nodes; i++ ) {
		Receive( i );
		lowest_right = GetLL( i );
		lowest_left = GetLL( i );
		lowest_middle = GetLL( i );
		sum = GetLL( i );
		best_antisandwich = min( best_antisandwich, prev_lowest_part + lowest_left );   //we can end the antisandwich in this node's block
		total_sandwich += sum;
		prev_lowest_part += sum;							//we can widen the antisandwich with this node's block
		prev_lowest_part = min( prev_lowest_part, lowest_right );			//we can substitute the antisandwich for the one starting in this block and going on...
		best_antisandwich = min( best_antisandwich, lowest_middle );			//...or starting and ending in this block
	}

	cout << total_sandwich - best_antisandwich << endl;

	return 0;

}