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
#include "message.h"
#include "kanapka.h"
#include <stdio.h>
#define MAX(a,b) ((a) > (b) ? a : b)
#define MIN(a,b) ((a) < (b) ? a : b)

int main()
{
    long long N = GetN();
    long long begin = (MyNodeId() * N) / NumberOfNodes();
    long long end = ((MyNodeId() + 1) * N) / NumberOfNodes();

    //# part1 - solve subproblems
    long long ix, sum = 0, contMin = 0, prefMin = 0, suffMin;
    long long prefMax = 0, temp = 0;

    for (ix = begin; ix < end; ix++)
    {
        int t = GetTaste(ix);
        temp = (temp < 0) ? (temp + t) : t;
        sum += t;
        contMin = MIN(contMin, temp);
        prefMin = MIN(prefMin, sum);
        prefMax = MAX(prefMax, sum);
    }
    suffMin = sum - prefMax;


    //#part2 - receive the data
    int i;
    long long data[128][4];

    if (MyNodeId() > 0){
        PutLL(0, sum);
        PutLL(0, contMin);
        PutLL(0, prefMin);
        PutLL(0, suffMin);
        Send(0);
    }
    else{
        data[0][0] = sum;
        data[0][1] = contMin;
        data[0][2] = prefMin;
        data[0][3] = suffMin;
        for (i = 1; i < NumberOfNodes(); ++i) {
            int inst = Receive(-1);
            data[inst][0] = GetLL(inst);
            data[inst][1] = GetLL(inst);
            data[inst][2] = GetLL(inst);
            data[inst][3] = GetLL(inst);
        }
    }


    //#part3 - calculate the answer
    long long ans = 0;
    long long sumAll = 0;

    if (MyNodeId() == 0){
        for (i = 0; i < NumberOfNodes(); ++i) {
            ans = MIN(ans, data[i][0]);
            ans = MIN(ans, data[i][1]);
            ans = MIN(ans, data[i][2]);
            ans = MIN(ans, data[i][3]);
            sumAll += data[i][0];
        }

        long long pp = MIN(data[0][0], data[0][3]);
        for (i = 1; i < NumberOfNodes(); ++i) {
            ans = MIN(ans, pp + data[i][2]);
            pp = MIN(pp + data[i][0], data[i][3]);
        }

        ans = MIN(ans, sumAll);

        printf("%lld\n",sumAll - ans);
    }


    return 0;
}