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

#define MAX_INST 200

int main () {
    long long N = GetN();

    long long id = MyNodeId();
    long long nodes = NumberOfNodes();

    long long p = (MyNodeId() * N) / NumberOfNodes();
    long long q = ((MyNodeId() + 1) * N) / NumberOfNodes();

    long long sum = 0;
    long long first_pref = 0;
    long long first_suf = 0;
    long long second_pref = 0;
    long long second_suf = 0;

    for (long long i = p; i < q; i++) {
        sum += GetTaste(i);
        second_suf = min(second_suf, sum);
        if (sum > first_pref) {
            first_pref = sum;
            second_suf = sum;
        }
        if (sum <= first_suf) {
            first_suf = sum;
            second_pref = first_pref;
        }
    }
    first_suf = sum - first_suf;
    second_suf = sum - second_suf;

    if (id > 0) {
        PutLL(0, sum);
        PutLL(0, first_pref);
        PutLL(0, second_pref);
        PutLL(0, first_suf);
        PutLL(0, second_suf);
        Send(0);
    } else {

        long long SUM[MAX_INST];
        long long FIRST_PREF[MAX_INST];
        long long FIRST_SUF[MAX_INST];
        long long SECOND_PREF[MAX_INST];
        long long SECOND_SUF[MAX_INST];

        SUM[0] = sum;
        FIRST_PREF[0] = first_pref;
        FIRST_SUF[0] = first_suf;
        SECOND_PREF[0] = second_pref;
        SECOND_SUF[0] = second_suf;
        long long total = sum;

        for (int i = 1; i < nodes; i++) {
            int inst = Receive(-1);
            SUM[inst] = GetLL(inst);
            FIRST_PREF[inst] = GetLL(inst);
            SECOND_PREF[inst] = GetLL(inst);
            FIRST_SUF[inst] = GetLL(inst);
            SECOND_SUF[inst] = GetLL(inst);
            total += SUM[inst];
        }

        long long first_pref = FIRST_PREF[0];
        long long second_pref = SECOND_PREF[0];
        long long first_suf = FIRST_SUF[0] - SUM[0];
        long long second_suf = SECOND_SUF[0] - SUM[0];
        long long sum = 0;

        for (int i = 0; i < nodes-1; i++) {
            sum += SUM[i];
            long long sum_next = sum + SUM[i+1];
            second_suf = max(second_suf, FIRST_SUF[i+1] - sum_next);
            if (FIRST_SUF[i+1] - sum_next >= first_suf) {
                first_suf = FIRST_SUF[i+1] - sum_next;
                second_pref = max(first_pref, SECOND_PREF[i+1] + sum);
            }
            if (sum + FIRST_PREF[i+1] > first_pref) {
                first_pref = sum + FIRST_PREF[i+1];
                second_suf = SECOND_SUF[i+1] - sum_next;
            }
        }
        first_suf += total;
        second_suf += total;

        printf("%lld\n", max(first_pref + second_suf, second_pref + first_suf));
    }
}