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
#include <cstdio>

#include "message.h"
#include "maklib.h"

const long long ROOT_NODE = 0;

inline void updateIfGreater(long long &a, long long b) {
    if (a < b) {
        a = b;
    }
}

long long getSum(int start, int end) {
    long long sum = 0;
    for(int i = start + 1; i <= end; ++i) {
        sum += ElementAt(i);
    }
    return sum;
}

long long getMaxSum(int start, int end) {
    long long maxSum = 0, sum = 0;
    for(int i = start + 1; i <= end; ++i) {
        sum += ElementAt(i);
        if (sum < 0) {
            sum = 0;
        }
        updateIfGreater(maxSum, sum);
    }
    return maxSum;
}

long long getMaxLeftSum(int start, int end) {
    long long maxSum = 0, sum = 0;
    for(int i = start + 1; i <= end; ++i) {
        sum += ElementAt(i);
        updateIfGreater(maxSum, sum);
    }
    return maxSum;
}

long long getMaxRightSum(int start, int end) {
    long long maxSum = 0, sum = 0;
    for(int i = end; i > start; --i) {
        sum += ElementAt(i);
        updateIfGreater(maxSum, sum);
    }
    return maxSum;
}

int main() {
    int n, a, b;
    long long maxSum, maxLeftSum, maxRightSum, sum;
    long long maxSumAcc, maxLeftSumAcc, maxRightSumAcc, sumAcc;
    long long nextMaxSum, nextMaxLeftSum, nextMaxRightSum, nextSum;

    n = Size() / NumberOfNodes();
    a = MyNodeId() * n;
    if (MyNodeId() + 1 == NumberOfNodes()) {
        b = Size();
    } else {
        b = a + n;
    }

    sum = getSum(a, b);
    maxSum = getMaxSum(a, b);
    maxLeftSum = getMaxLeftSum(a, b);
    maxRightSum = getMaxRightSum(a, b);

    if (MyNodeId() == ROOT_NODE) {

        for (int nodeId = 0; nodeId < NumberOfNodes(); ++nodeId) {

            if (nodeId != ROOT_NODE) {

                sumAcc = sum;
                maxSumAcc = maxSum;
                maxLeftSumAcc = maxLeftSum;
                maxRightSumAcc = maxRightSum;

                Receive(nodeId);
                nextSum = GetLL(nodeId);
                nextMaxSum = GetLL(nodeId);
                nextMaxLeftSum = GetLL(nodeId);
                nextMaxRightSum = GetLL(nodeId);

                sumAcc += nextSum;
                maxRightSumAcc += nextSum;

                updateIfGreater(maxLeftSumAcc, sum + nextMaxLeftSum);
                updateIfGreater(maxRightSumAcc, nextMaxRightSum);

                updateIfGreater(maxSumAcc, nextMaxSum);
                updateIfGreater(maxSumAcc, maxLeftSumAcc);
                updateIfGreater(maxSumAcc, maxRightSumAcc);
                updateIfGreater(maxSumAcc, maxRightSum + nextMaxLeftSum);

                sum = sumAcc;
                maxSum = maxSumAcc;
                maxLeftSum = maxLeftSumAcc;
                maxRightSum = maxRightSumAcc;

            }

        }

        printf("%llu\n", maxSum);

    } else {
        PutLL(ROOT_NODE, sum);
        PutLL(ROOT_NODE, maxSum);
        PutLL(ROOT_NODE, maxLeftSum);
        PutLL(ROOT_NODE, maxRightSum);
        Send(ROOT_NODE);
    }
}