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

typedef long long LL;

int main()
{
    int id = MyNodeId(), num = NumberOfNodes();
    LL n = Size();

    int i0 = (id * n) / num;
    int i1 = ((id+1) * n) / num;
    
    LL sum = 0, mins = 0, maxs = 0, w = 0;
    for (int i=i0; i<i1; i++)
    {
        sum += ElementAt(i+1);
        if (sum < mins) mins = sum;
        if (sum > maxs) maxs = sum;
        w = max(w, sum - mins);
    }
    
    if (id > 0)
    {
        PutLL(0, sum);
        PutLL(0, mins);
        PutLL(0, maxs);
        PutLL(0, w);
        Send(0);
    }
    else
    {
        for (int i=1; i<num; i++)
        {
            Receive(i);
            LL _sum = GetLL(i);
            LL _mins = GetLL(i);
            LL _maxs = GetLL(i);
            LL _w = GetLL(i);
            w = max(w, max(_w, sum + _maxs - mins));
            maxs = max(maxs, sum + _maxs);
            mins = min(mins, sum + _mins);
            sum += _sum;
        }
        printf("%lld\n", w);
    }
    return 0;
}