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

int main(int argc, char** argv) {
    int number_of_nodes = NumberOfNodes();
    int my_node = MyNodeId();
    long long n = GetN();

    long long number_per_node = n/number_of_nodes;
    long long nodes_with_addition = n - number_of_nodes*number_per_node;

    long long start_index;
    long long end_index;

    if (my_node < nodes_with_addition) {
    	start_index = (number_per_node + 1) * my_node;
    	end_index = start_index + number_per_node + 1;
    } else {
    	start_index = number_per_node * my_node + nodes_with_addition;
    	end_index = start_index + number_per_node;
    }

    if (start_index > n) {
		start_index = n;
	}
	if (end_index > n) {
		end_index = n;
	}

    if (start_index != end_index) {
    	long long max_prefix = 0;
    	long long sum = GetTaste(start_index);
    	long long max_sufix = 0;

    	long long temp;

    	for (long long index = start_index + 1; index < end_index; index++) {
    		temp = GetTaste(index);

    		if (max_sufix + temp < 0) {
    			if (max_prefix < sum) {
    				max_prefix = sum;
    			}
    			max_sufix = 0;
    		} else {
    			if (max_prefix + max_sufix + temp < sum) {
    				max_prefix = sum;
    				max_sufix = 0;
    			} else {
    				max_sufix += temp;
    			}
    		}
    		sum += temp;
    	}

    	int multiplier = 1;
    	int temp_my_node = my_node;
    	int should_receive_or_send = true;
    	while(should_receive_or_send) {
			if (temp_my_node & 1) {
				int target = (temp_my_node - 1)*multiplier;
				PutLL(target, max_prefix);
				PutLL(target, sum);
				PutLL(target, max_sufix);
				Send(target);
				should_receive_or_send = false;
			} else {
				int source = (temp_my_node + 1)*multiplier;
				if (source >= number_of_nodes || source >= n) {
					if (my_node == 0) {
						if (max_prefix + max_sufix > sum) {
							sum = max_prefix + max_sufix;
						}
						std::cout << sum << std::endl;
						should_receive_or_send = false;
					}
				} else {
					Receive(source);
					long long temp_max_prefix = GetLL(source);
					long long temp_sum = GetLL(source);
					long long temp_max_sufix = GetLL(source);

					if (max_sufix + temp_sum < temp_max_sufix) {
						if (max_prefix < sum + temp_max_prefix) {
							max_prefix = sum + temp_max_prefix;
						}
						max_sufix = temp_max_sufix;
					} else {
						if (max_prefix + max_sufix + temp_sum < sum + temp_max_prefix + temp_max_sufix) {
							max_prefix = sum + temp_max_prefix;
							max_sufix = temp_max_sufix;
						} else {
							max_sufix += temp_sum;
						}
					}
					sum += temp_sum;
				}
			}
			multiplier *= 2;
			temp_my_node /= 2;
    	}


    }

    return 0;
}