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

#include <iostream>

//#define DEBUG(x) x

using namespace std;

using MyNum = long long;
struct Evaluation {
    MyNum m1;
    MyNum m2;
    MyNum m3;
};

Evaluation min_subarray(const MyNum begin, const MyNum end) {
    MyNum min_ending_here, min_so_far;
    min_ending_here = min_so_far = GetTaste(begin);

    MyNum idx_begin, idx_end;
    idx_begin = idx_end = begin;

    MyNum x;
    for (auto i = begin + 1; i < end; ++i) {
        x = GetTaste(i);
        if (x < min_ending_here + x) {
            min_ending_here = x;
            idx_begin = i;
            idx_end = i;
        } else {
            min_ending_here += x;
        }
        if (min_so_far >= min_ending_here) {
            min_so_far = min_ending_here;
            idx_end = i;
        }
    }

    Evaluation eval;
    eval.m1 = 0;
    eval.m3 = 0;
    eval.m2 = min_so_far;
    if (idx_begin != begin) {
        for (auto i = begin; i < idx_begin; ++i)
            eval.m1 += GetTaste(i);
    }
    if (idx_end != end) {
        for (auto i = idx_end + 1; i < end; ++i)
            eval.m3 += GetTaste(i);
    }
    return eval;
}

MyNum min_subarray_final(long long int *tab) {
    MyNum min_ending_here, min_so_far;
    min_ending_here = min_so_far = tab[0];
    MyNum sum = tab[0];
    for (auto i = 1; i < 3 * NumberOfNodes(); ++i) {
        sum += tab[i];
        min_ending_here = min(tab[i], min_ending_here + tab[i]);
        min_so_far = min(min_so_far, min_ending_here);
    }
    if (min_so_far < 0)
        sum -= min_so_far;
    return (sum > 0) ? sum : 0;
}

int main() {
//    DEBUG(if (MyNodeId() == 0)
//        cout << "START\n";)

    auto size = GetN() / NumberOfNodes();
    if (GetN() % NumberOfNodes() != 0)
        size += 1;
    MyNum begin = size * MyNodeId();
    if (begin >= GetN()) {
        PutLL(0, 0);
        PutLL(0, 0);
        PutLL(0, 0);
        Send(0);
        return 0;
    }
    MyNum end = begin + size;
    end = (end <= GetN()) ? end : GetN();

    auto eval = min_subarray(begin, end);
    if (MyNodeId() != 0) {
        PutLL(0, eval.m1);
        PutLL(0, eval.m2);
        PutLL(0, eval.m3);
        Send(0);
        return 0;
    }

    auto *tab = new long long int[3 * NumberOfNodes()];
    tab[0] = eval.m1;
    tab[1] = eval.m2;
    tab[2] = eval.m3;
//    DEBUG(cout << "{0} " << eval.m1 << " " << eval.m2 << " " << eval.m3 << endl;)
    for (auto i = 1; i < NumberOfNodes(); ++i) {
        Receive(i);
        tab[3 * i + 0] = GetLL(i);
        tab[3 * i + 1] = GetLL(i);
        tab[3 * i + 2] = GetLL(i);
//        DEBUG(cout << "{" << i << "} " << tab[3 * i + 0] << " " << tab[3 * i + 1] << " " << tab[3 * i + 2] << endl;)
    }

    cout << min_subarray_final(tab) << endl;
    delete [] tab;
    return 0;
}