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
// Karol Kosinski
#include "message.h"
#include "kanapka.h"
#include <cstdio>
#include <algorithm>
//#define DEBUG(x...) printf(x);
#define DEBUG(x...)
using namespace std;
typedef long long LG;

struct segment {

        segment(LG x): CI(x) {
                LG v = min(x, 0LL);
                LI = RI = SI = v;
        }

        segment(LG ci, LG li, LG ri, LG si):
                CI(ci), LI(li), RI(ri), SI(si) {}

        void extend(const segment &b) {
                segment a(*this);
                CI = a.CI + b.CI;
                LI = min(a.LI, a.CI + b.LI);
                RI = min(a.RI + b.CI, b.RI);
                SI = min(min(a.SI, b.SI), a.RI + b.LI);
        }

        LG CI, LI, RI, SI;
};

int main() {
        int nodes = NumberOfNodes();
        int id = MyNodeId();
        LG n = GetN();
        nodes = min(nodes, (int)n);
        if( id >= nodes ) return 0;
        LG start = n * id / nodes;
        LG finish = n * (id + 1) / nodes;

        segment seg(0);
        for(LG i = start; i < finish; ++i) {
                LG x = GetTaste(i);
                segment aux(x);
                seg.extend(aux);
        }
        DEBUG("s(%3lld) f(%3lld):  ", start, finish);
        DEBUG("CI=%4lld LI=%4lld RI=%4lld SI=%4lld\n",
                seg.CI, seg.LI, seg.RI, seg.SI);

        if( id != 0 ) {
                PutLL(0, seg.SI);
                PutLL(0, seg.RI);
                PutLL(0, seg.LI);
                PutLL(0, seg.CI);
                Send(0);
        } else {
                for(int i = 1; i < nodes; ++i) {
                        Receive(i);
                        segment aux(GetLL(i), GetLL(i), GetLL(i), GetLL(i));
                        DEBUG("***  +   %2d:  ", i);
                        DEBUG("CI=%4lld LI=%4lld RI=%4lld SI=%4lld\n",
                                aux.CI, aux.LI, aux.RI, aux.SI);
                        seg.extend(aux);
                        DEBUG("*** Inst %2d:  ", i);
                        DEBUG("CI=%4lld LI=%4lld RI=%4lld SI=%4lld\n",
                                seg.CI, seg.LI, seg.RI, seg.SI);
                }
                printf("%lld\n", seg.CI - seg.SI);
        }
        return 0;
}