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
/* 2014
 * Maciej Szeptuch
 * II UWr
 */
#include "maklib.h"
#include "message.h"

#include <cstdio>
#include <algorithm>

using namespace std;

long long   node,
            nodes,
            size,
            range,
            stages;

long long   prefix,
            suffix,
            whole,
            inside;

void moveData(long long s);
void mergeData(long long s);

int main(void)
{
    node    = MyNodeId();
    nodes   = NumberOfNodes();

    size    = Size();
    range   = (size + nodes - 1) / nodes;

    nodes = min(nodes, size);

    // Too many workers, don't need that much
    if(node >= nodes)
        return 0;

    while((1 << stages) < nodes)
        ++ stages;

    // FIRST STAGE
    long long _min = 0;
    for(long long s = node * range, e = (node + 1) * range; s < e && s < size; ++ s)
    {
        whole += ElementAt(s + 1);
        _min = min(_min, whole);

        prefix = max(prefix, whole);
        inside = max(inside, whole - _min);
    }

    suffix = whole - _min;
    moveData(0);

    // GATHERING STAGES
    for(long long stage = 1; (node % (1 << stage)) == 0 && stage <= stages; ++ stage)
    {
        mergeData(stage);
        moveData(stage);
    }

    if(!node)
        printf("%lld\n", inside);

    return 0;
}

inline
void moveData(long long s)
{
    long long senders     = (1 << (s + 1));
    long long recipient   = node - (1 << s);
    if(node % senders)
    {
        PutLL(recipient, prefix);
        PutLL(recipient, suffix);
        PutLL(recipient, whole);
        PutLL(recipient, inside);
        Send(recipient);
        //fprintf(stderr, "%lld/%lld sending to %lld\n", s, node, recipient);
    }

    //fprintf(stderr, "%lld/%lld: %lld %lld %lld %lld\n", s, node, prefix, suffix, whole, inside);
}

inline
void mergeData(long long s)
{
    long long sender = node + (1 << (s - 1));
    if(sender >= nodes)
        return;

    Receive(sender);
    //fprintf(stderr, "%lld reading from %lld\n", node, sender);
    long long   _prefix,
                _suffix,
                _whole,
                _inside;

    _prefix = GetLL(sender);
    _suffix = GetLL(sender);
    _whole  = GetLL(sender);
    _inside = GetLL(sender);

    inside = max(inside, _inside);
    inside = max(inside, suffix + _prefix);

    prefix = max(prefix, whole + _prefix);
    suffix = max(_whole + suffix, _suffix);
    whole += _whole;

    inside = max(inside, prefix);
    inside = max(inside, suffix);
    inside = max(inside, whole);
}

/*
0 1 2 3 4 5 6 7 8 9
0 # 2 # 4 # 6 # 8 #
0 # # # 4 # # # 8 #
0 # # # # # # # 8 #
0 # # # # # # # # #
*/