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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include "message.h"
#include "kanapka.h"
#include <stdint.h>
#include <stdio.h>

struct Results
{
    int64_t total;
    int64_t rightMax;
    int64_t leftMax;
    int64_t localMax;

    int64_t globalLeftMax;
    int64_t globalTotal;

    void send()
    {
        PutLL(0, total);
        PutLL(0, rightMax);
        PutLL(0, leftMax);
        PutLL(0, localMax);
        Send(0);
    }

    void receive(int sender)
    {
        total = GetLL(sender);
        rightMax = GetLL(sender);
        leftMax = GetLL(sender);
        localMax = GetLL(sender);
    }
};

Results compute(uint64_t fromIndex, uint64_t toIndex)
{
    uint64_t length = toIndex - fromIndex;
    int64_t* maxes = new int64_t[length];

    int64_t max = 0;
    int64_t leftTotal = 0;
    int64_t leftMax = 0;
    for (uint64_t i = 0; i < length; ++i)
    {
        leftTotal += GetTaste(fromIndex + i);
        if (leftTotal > leftMax)
            leftMax = leftTotal;
        maxes[i] = leftMax;
    }

    int64_t rightTotal = 0;
    int64_t rightMax = 0;
    for (uint64_t i = length - 1; i > 0; --i)
    {
        rightTotal += GetTaste(fromIndex + i);
        if (rightTotal > rightMax)
            rightMax = rightTotal;

        int64_t current = rightMax + maxes[i - 1];
        if (current > max)
            max = current;
    }

    Results result;
    result.total = leftTotal;
    result.rightMax = rightMax;
    result.leftMax = leftMax;
    result.localMax = max;
    delete[] maxes;
    return result;
}

int main()
{
    if (GetN() < 1000)
    {
        if (MyNodeId() == 0)
        {
            auto result = compute(0, GetN());
            printf("%ld\n", result.localMax);
        }
        return 0;
    }

    uint64_t chunk = GetN() / NumberOfNodes();
    uint64_t from = MyNodeId() * chunk;
    uint64_t to = from + chunk;
    if (MyNodeId() == NumberOfNodes() - 1)
        to = GetN();

    auto localResult = compute(from, to);
    if (MyNodeId() != 0)
    {
        localResult.send();
        return 0;
    }

    Results* result = new Results[NumberOfNodes()];
    result[0] = localResult;

    int i = 1;
    while (i < NumberOfNodes())
    {
        int sender = Receive(-1);
        result[sender].receive(sender);
        ++i;
    }

    int64_t total = 0;
    int64_t max = 0;
    for (int i = 0; i < NumberOfNodes(); ++i)
    {
        if (total + result[i].leftMax > max)
            max = total + result[i].leftMax;

        total += result[i].total;
        result[i].globalLeftMax = max;
        result[i].globalTotal = total;
    }

    int64_t globalMaximum = 0;
    total = 0;
    max = 0;
    for (int i = NumberOfNodes() - 1; i > 0; --i)
    {
        if (total + result[i].rightMax > max)
            max = total + result[i].rightMax;

        int64_t check = max + result[i - 1].globalLeftMax;
        if (check > globalMaximum)
            globalMaximum = check;

        check = result[i].localMax + total + result[i - 1].globalTotal;
        if (check > globalMaximum)
            globalMaximum = check;

        total += result[i].total;
    }

    printf("%lu\n", globalMaximum);
    delete[] result;
    return 0;
}