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
#include <algorithm>
#include <iostream>
#include <vector>

#include "kanapka.h"
#include "message.h"


typedef long long LL;

struct Sammich {
        LL sum_tastes;      //sum of all sectors of this sammich
        LL bad_taste;       //sum of values of not-eat sectors
        LL bad_left;        //sum of not-eat sectors from left
        LL bad_right;       //sum of not-eat sectors from right
};

Sammich readSammich(LL i) {
        LL taste = GetTaste(i);
        Sammich sammich;
        sammich.sum_tastes = taste;
        sammich.bad_taste = sammich.bad_left = sammich.bad_right = std::min(taste, LL(0));
        return sammich;
}

Sammich operator+(const Sammich& left, const Sammich& right) {
        Sammich sammich;

        sammich.sum_tastes = left.sum_tastes + right.sum_tastes;
        sammich.bad_taste  = std::min(std::min(left.bad_taste, right.bad_taste), left.bad_right+right.bad_left);
        sammich.bad_left   = std::min(left.bad_left, left.sum_tastes + right.bad_left);
        sammich.bad_right  = std::min(right.bad_right, right.sum_tastes + left.bad_right);
        return sammich;
}

Sammich getSammich(LL start, LL end) {
        Sammich s = readSammich(start);
        for(LL i=start+1; i<end; i++) {
                s = s + readSammich(i);
        }
        return s;
}

Sammich receive(LL nodeId) {
        Receive((int) nodeId);
        Sammich sammich;
        sammich.sum_tastes = GetLL(nodeId);
        sammich.bad_taste = GetLL(nodeId);
        sammich.bad_left = GetLL(nodeId);
        sammich.bad_right = GetLL(nodeId);
        return sammich;
}

void send(int nodeId, const Sammich& sammich) {
        PutLL(nodeId, sammich.sum_tastes);
        PutLL(nodeId, sammich.bad_taste);
        PutLL(nodeId, sammich.bad_left);
        PutLL(nodeId, sammich.bad_right);
        Send(nodeId);
}

int main(void) {
        LL nodeId = MyNodeId();
        LL numberOfNodes = NumberOfNodes();
        LL n = GetN();

        numberOfNodes = std::min(n, numberOfNodes);

        if (nodeId >= numberOfNodes) {
           return 0;
        }

        LL size = n/numberOfNodes;
        Sammich sammich = getSammich(size*nodeId, size*(nodeId+1));

        if (nodeId == 0) {
                for(int i=1; i<numberOfNodes; i++) {
                        sammich = sammich + receive(i);
                }
        } else {
                send(0, sammich);
        }

        std::cout << sammich.sum_tastes - sammich.bad_taste << std::endl;

        return 0;
}