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
#include <iostream>
#include <vector>
#include <utility>
#include <stack>

#include "message.h"
#include "kanapka.h"

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);


    long long numberOfNodes = NumberOfNodes();
    long long myNodeId = MyNodeId();

    long long n = GetN();
    long long global_best = 0;
    long long global_total = 0;

    long long this_instance_lower = n * myNodeId / numberOfNodes;
    long long this_instance_upper = n * (myNodeId+1) / numberOfNodes;
    long long this_instance_range = this_instance_upper - this_instance_lower;

    vector<int> sandwitch_part(this_instance_range);

    long long best_prefix=0, best_sufix=0, best_mixed=0, total=0;

    for(int i=0 ; i<this_instance_range ; i++) {
        sandwitch_part[i] = GetTaste( i + this_instance_lower );
        total += sandwitch_part[i];
    }

    long long current_prefix=0;
    if( best_prefix < total ) {
        best_prefix = total;
    }
    if( best_sufix < total ) {
        best_sufix = total;
    }
    if( best_mixed < total ) {
        best_mixed = total;
    }
    for(int i=0 ; i<this_instance_range ; i++) {
        current_prefix += sandwitch_part[i];

        if( best_prefix < current_prefix ) {
            best_prefix = current_prefix;
        }
        if( best_sufix < total-current_prefix) {
            best_sufix = total-current_prefix;
        }
        if( best_mixed < best_prefix + total - current_prefix ) {
            best_mixed = best_prefix + total - current_prefix;
        }
    }
    if( best_mixed < best_prefix ) {
        best_mixed = best_prefix;
    }
    if( best_mixed < best_sufix ) {
        best_mixed = best_sufix;
    }
    if( best_mixed < total ) {
        best_mixed = total;
    }
    if( myNodeId>0 ) {
        PutLL(0, best_prefix);
        PutLL(0, best_sufix);
        PutLL(0, best_mixed);
        PutLL(0, total);
        Send(0);
        //cout << "Node " << myNodeId << " sent message" << endl;
    } else {
        vector<long long> prefix_vector(numberOfNodes);
        vector<long long> sufix_vector(numberOfNodes);
        vector<long long> mixed_vector(numberOfNodes);
        vector<long long> total_vector(numberOfNodes);
        vector<long long> partial_sum_vector(numberOfNodes);

        prefix_vector[0] = best_prefix;
        sufix_vector[0] = best_sufix;
        mixed_vector[0] = best_mixed;
        total_vector[0] = total;
        global_total = total;
        partial_sum_vector[0] = total;
        for( int i=1 ; i<numberOfNodes ; i++ ) {
            Receive(i);
            prefix_vector[i] = GetLL(i);
            sufix_vector[i] = GetLL(i);
            mixed_vector[i] = GetLL(i);
            total_vector[i] = GetLL(i);
            global_total += total_vector[i];
            partial_sum_vector[i] = global_total;
        }

        if( global_best < global_total ) {
            global_best = global_total;
        }

        for( int i=0 ; i<numberOfNodes ; i++ ) {
            if( global_best < global_total - total_vector[i] + mixed_vector[i] ) {
                global_best = global_total - total_vector[i] + mixed_vector[i];
            }
        }


        for( int i=0 ; i<numberOfNodes ; i++ ) {
            for( int j=i+1 ; j<numberOfNodes ; j++ ) {
                long long this_iteration_candidate = prefix_vector[i] + sufix_vector[j]
                    + global_total - partial_sum_vector[j] + ((i>0)?(partial_sum_vector[i-1]):0);
                if( global_best < this_iteration_candidate ) {
                    global_best = this_iteration_candidate;
                }
            }
        }
        cout << global_best << endl;
        
    }
    //cout << myNodeId <<" finished" << endl;
    return 0;
}