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
96
97
98
99
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include "kanapka.h"
#include "message.h"

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define PB push_back

using namespace std;

typedef long long int LLI;
typedef vector < LLI > VL;

/*************************************************************************/

int main()
{
    ios_base::sync_with_stdio(0);

    int n = GetN();

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

    int len = (n + nodes - 1) / nodes;
    int L = id * len,
        R = L + len;

    LLI sum = 0,
        pref = 0,
        suff = 0,
        best = 0,
        curr = 0;

    for (int i = L; i < min(R,n); i++)
    {
        int v = GetTaste(i);

        curr = min(curr + v, 0LL);
        best = min(best, curr);

        sum += v;
        pref = min(pref, sum);
        suff = max(suff, sum);
    }

    suff = sum - suff;

    if (id)
    {
        PutLL(0, sum);
        PutLL(0, pref);
        PutLL(0, suff);
        PutLL(0, best);
        Send(0);
    }
    else
    {
        VL Sum(1,sum),
           Pref(1,pref),
           Suff(1,suff);

        LLI ans = best;

        FOR(i,1,nodes-1)
        {
            Receive(i);

            sum = GetLL(i);
            pref = GetLL(i);
            suff = GetLL(i);
            best = GetLL(i);

            Sum.PB(sum);
            Pref.PB(pref);
            Suff.PB(suff);
            ans = min(ans, best);
        }

        FOR(i,1,nodes-1)
            Sum[i] += Sum[i-1];

        FOR(i,0,nodes-1) FOR(j,i+1,nodes-1)
        {
            LLI here = Suff[i] + Pref[j] +
                       (j ? Sum[j-1] : 0) - Sum[i];

            ans = min(ans, here);
        }

        cout << Sum.back() - ans;
    }

    return 0;
}

/*************************************************************************/