#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; }
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; } |