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

int instances;
int nodeid;
int n, b, e;
long long int left_val, right_val, middle_val;
long long int max_left, max_right;
long long int cleft, cright, cmid;
int lindex, rindex;
long long int gap;
int gap_start, gap_end;

int main() {
    instances = NumberOfNodes();
    nodeid = MyNodeId();

    n = GetN();
    b = (n/instances)*nodeid;
    e = (n/instances)*(nodeid+1);
    if (nodeid == instances-1) e = n;

    left_val = right_val = middle_val = 0;
    cleft = cright = cmid = 0;
    lindex = b; rindex = e-1;
    for (int i = b; i < e; i++) {
        cleft += GetTaste(i);
        cright += GetTaste(b+e-i-1);
        if (cleft > left_val) {
            left_val = cleft;
            lindex = i;
        }
        if (cright > right_val) {
            right_val = cright;
            rindex = b+e-i-1;
        }
    }

    cmid = cright; // == cleft, or at least should
    gap_start = 0; gap_end = 0;
    gap = 0; long long int current_gap = 0;
    long long int lbuff = 0, rbuff = 0;
    if (lindex < rindex) goto infoexchange;
    for (int i = b; i < e; i++) {
        current_gap += GetTaste(i);
        lbuff -= GetTaste(i);
        if (lbuff < 0) {
            current_gap += lbuff;
            lbuff = 0;
        }
        if (current_gap < gap) gap = current_gap;
    }
    middle_val = cleft - gap;

    if (instances == 1) {
        if (right_val > middle_val) middle_val = right_val;
        if (left_val > middle_val) middle_val = left_val;
        printf("%lli", middle_val);
        return 0;
    }
    infoexchange:
    if (nodeid == 0) {
        PutLL(1, left_val);
        PutLL(1, left_val);
        Send(1);
    } else {
        Receive(nodeid-1);
        long long int received = GetLL(nodeid-1);
        left_val += received;
        middle_val += received;
        received = GetLL(nodeid-1);
        max_left =  (received > left_val) ? received : left_val;
        if (nodeid < instances-1) {
            PutLL(nodeid+1, left_val);
            PutLL(nodeid+1, max_left);
            Send(nodeid+1);
        }
    }
    if (nodeid == instances-1) {
        PutLL(nodeid-1, right_val);
        PutLL(1, left_val);
        Send(nodeid-1);
    } else {
        Receive(nodeid+1);
        long long int received = GetLL(nodeid+1);
        right_val += received;
        middle_val += received;
        received = GetLL(nodeid-1);
        max_right =  (received > right_val) ? received : right_val;
        if (nodeid > 0) {
            PutLL(nodeid-1, right_val);
            PutLL(nodeid-1, max_right);
            Send(nodeid-1);
        }
    }
    if (max_right > middle_val) middle_val = max_right;
    if (max_left > middle_val) middle_val = max_left;
    if (nodeid == 0) {
        PutLL(1, middle_val);
        Send(1);
    } else {
        Receive(nodeid-1);
        long long int received = GetLL(nodeid-1);
        if (received > middle_val) middle_val = received;
        if (nodeid < instances -1) {
            PutLL(nodeid+1, middle_val);
            Send(nodeid+1);
        }
    }
    if (nodeid != instances -1) {
        printf("%lli", middle_val);
    }
    return 0;    
}