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

#include <cstdlib>
#include <iostream>
using namespace std;

struct subseq_t {
    long long total;
    long long min_prefix;
    long long min_suffix;
    long long min_infix;
};

subseq_t solve(const long long begin, const long long end) {
    subseq_t ret = {};

    for (long long i = begin; i < end; ++i) {
        long long taste = GetTaste(i);
        ret.min_infix  = min<long long>(ret.min_infix, (ret.min_suffix + taste));
        ret.min_suffix = min<long long>(0, (ret.min_suffix + taste));
        ret.min_prefix = min<long long>(ret.min_prefix, (ret.total + taste));
        ret.total += taste;
    }
     
    return ret;
}

subseq_t merge(const subseq_t *solutions, const int count) {
    subseq_t ret = solutions[0];

    for (int i = 1; i < count; ++i) {
        ret.min_infix  = min<long long>(ret.min_infix, min<long long>((ret.min_suffix + solutions[i].min_prefix), solutions[i].min_infix));
        ret.min_suffix = min<long long>((ret.min_suffix + solutions[i].total), solutions[i].min_suffix);
        ret.min_prefix = min<long long>(ret.min_prefix, (ret.total + solutions[i].min_prefix));
        ret.total += solutions[i].total;
    }
     
    return ret;
}

int main() {
    long long N     = GetN();
    int node_count  = NumberOfNodes();
    int node_id     = MyNodeId();

    // MAP
    // get your subsequence
    long long start = (double)  node_id       / node_count * N;
    long long end   = (double) (node_id + 1)  / node_count * N;

    // solve your subsequence
    subseq_t seq = solve(start, end);

    // REDUCE
    if (node_id != 0) {
        // send solution to "master node"
        PutLL(0, seq.total);
        PutLL(0, seq.min_prefix);
        PutLL(0, seq.min_suffix);
        PutLL(0, seq.min_infix);
        Send(0); 
    } else {
        // wait for all solutions
        subseq_t *solutions = new subseq_t[node_count];
        solutions[0] = seq;
        for (int i = 1; i < node_count; ++i) {
            int from = Receive(-1);
            solutions[from].total       = GetLL(from);
            solutions[from].min_prefix  = GetLL(from);
            solutions[from].min_suffix  = GetLL(from);
            solutions[from].min_infix   = GetLL(from);
        }
        // get total result
        subseq_t total = merge(solutions, node_count);
        cout << max<long long>(0, (total.total - total.min_infix));
    }

    return 0;
}