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
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <unistd.h>

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

using namespace std;

long long get_total_sum(long long first, long long last) {
    long long result = 0;
    for (long long i = first; i <= last; i++) {
        result += GetTaste(i);
    }
    return result;
}

long long get_lowest_prefix(long long first, long long last) {
    long long curr_sum = 0;
    long long result = 0;
    for (long long i = first; i <= last; i++) {
        curr_sum += GetTaste(i);
        result = min(result, curr_sum);
    }
    return result;
}

long long get_lowest_sufix(long long first, long long last) {
    long long curr_sum = 0;
    long long result = 0;
    for (long long i = last; i >= first; i--) {
        curr_sum += GetTaste(i);
        result = min(result, curr_sum);
    }
    return result;
}

long long get_lowest_inside(long long first, long long last) {
    long long prev = 0;
    long long result = 0;
    for (long long i = first; i <= last; i++) {
        long long curr = GetTaste(i) + (prev < 0 ? prev : 0);
        result = min(result, curr);
        prev = curr;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);

    int nodes = NumberOfNodes();
    int my_id = MyNodeId();
    long long n = GetN();
    long long per_node = (n + nodes - 1)/nodes;
    long long first = per_node * my_id;
    long long last = min(n, per_node * (my_id + 1)) - 1;
    //cout << my_id << " " << first << " " << last << endl;
    if (my_id != 0) {
        PutLL(0, get_total_sum(first, last));
        //Send(0);
        PutLL(0, get_lowest_prefix(first, last));
        //Send(0);
        PutLL(0, get_lowest_sufix(first, last));
        //Send(0);
        PutLL(0, get_lowest_inside(first, last));
        Send(0);
    }
    else {
        vector<long long> total_sum(nodes), lowest_prefix(nodes), 
            lowest_sufix(nodes), lowest_inside(nodes);
        total_sum[0] = get_total_sum(first, last);
        lowest_prefix[0] = get_lowest_prefix(first, last);
        lowest_sufix[0] = get_lowest_sufix(first, last);
        lowest_inside[0] = get_lowest_inside(first, last);
        long long entire_sum;
        entire_sum = total_sum[0];
        for (int i = 1; i < nodes; i++) {
            Receive(i);
            total_sum[i] = GetLL(i);
            //cout << i << " ";
            //cout << total_sum[i] << " ";
            entire_sum += total_sum[i];
            lowest_prefix[i] = GetLL(i);
            //cout << lowest_prefix[i] << " ";
            lowest_sufix[i] = GetLL(i);
            //cout << lowest_sufix[i] << " ";
            lowest_inside[i] = GetLL(i);
            //cout << lowest_inside[i] << endl;
        }
        long long best_score = LLONG_MIN;
        for (int i = 0; i < nodes; i++) {
            best_score = max(best_score, entire_sum - lowest_inside[i]);
        }
        //cout << entire_sum << endl;
        //cout << best_score << endl;
        for (int i = 0; i < nodes-1; i++) {
            long long sum_inside = 0;
            for (int j = i+1; j < nodes; j++) {
                best_score = max(best_score, 
                    entire_sum - (lowest_sufix[i] + lowest_prefix[j] + sum_inside));
                sum_inside += total_sum[j];
            }
        }
        cout << best_score << '\n';
    }
    return 0;
}