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 "kanapka.h"
#include "message.h"
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

//#define DEBUG

int main() {
    long long N = GetN();
    // Faza pierwsza.
    long long poczatek = (MyNodeId() * N) / NumberOfNodes();
    long long koniec = ((MyNodeId() + 1) * N) / NumberOfNodes();
    
    LL sl = 0, akt_max = 0, b = 0, maxb = 0, sum = 0, minsl = 0, maxsl = 0;

    for (long long i = poczatek; i < koniec; ++i) {
        long long kolejna = GetTaste(i);
        sl += kolejna;
        if (i == poczatek) {
            akt_max = sl;
            maxsl = sl;
            minsl = sl;
        }
        else {
            akt_max = max(akt_max, sl);
            maxsl = max(maxsl, sl);
            minsl = min(minsl, sl);
        }
        b = akt_max - sl;
        maxb = max(maxb, b);
    }
    
    sum = sl;

    if (MyNodeId() > 0) {
        PutLL(0, maxb);
        PutLL(0, sum);
        PutLL(0, minsl);
        PutLL(0, maxsl);
        Send(0);
    } 
    else {
        LL maxmaxb = 0, sumsum = 0, maxslpl = 0, minslpl = 0, poprz_best_maxslpl = 0, c = 0, maxc = 0;
        sumsum = sum;
        maxslpl = maxsl;
        minslpl = minsl;
        poprz_best_maxslpl = 0;
        c = 0;
        maxc = 0;
        maxmaxb = maxb;

#ifdef DEBUG
            fprintf(stderr, "0: maxb = %lld, sum = %lld, minsl = %lld, maxsl = %lld\n", 
                    maxb, sum, minsl, maxsl);
#endif
        for (int i = 1; i < NumberOfNodes(); ++i) {
            int instancja = Receive(i);
            maxb = GetLL(instancja);
            sum = GetLL(instancja);
            minsl = GetLL(instancja);
            maxsl = GetLL(instancja);

#ifdef DEBUG
            fprintf(stderr, "%d: maxb = %lld, sum = %lld, minsl = %lld, maxsl = %lld\n", 
                    instancja, maxb, sum, minsl, maxsl);
#endif

            poprz_best_maxslpl = max(poprz_best_maxslpl, maxslpl);

            maxslpl = sumsum + maxsl;
            minslpl = sumsum + minsl;
            sumsum += sum;
            c = poprz_best_maxslpl - minslpl;
            maxc = max(maxc, c);
            maxmaxb = max(maxmaxb, maxb);

#ifdef DEBUG
            fprintf(stderr, " poprz = %lld, sumsum = %lld, maxslpl = %lld, minslpl = %lld, c = %lld, maxc = %lld, maxmaxb = %lld\n", poprz_best_maxslpl, sumsum, maxslpl, minslpl, c, maxc, maxmaxb);
#endif
        }
        printf("%lld\n", max(0LL, sumsum + max(maxmaxb, maxc)));
    }

    return 0;
}