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
#include "kanapka.h"

#include "message.h"

#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define INF 1000000000000LL
LL nodes_cnt = 0;


struct RangeData {
  LL left;
  LL right;
  LL sum;
  LL maxSumLeft;
  LL maxSumRight;
  LL minSumLeft;
  LL minSumRight;
  LL minMiddleSum;

  RangeData(LL left, LL right) 
      : left(left)
      , right(right)
      , sum(0)
      , maxSumLeft(-INF)
      , maxSumRight(-INF)
      , minSumLeft(0)
      , minSumRight(0)
      , minMiddleSum(0)
    {}
};

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
/*
 *
 *
 */

RangeData compute_sum(LL left, LL right) {
    RangeData rd(left, right);
    rd.sum = GetTaste(left);
    LL current = 0ll;
    for (LL i=left+1; i < right; i++) {
       LL ti = GetTaste(i);
       rd.sum += ti;
       rd.maxSumLeft = max(rd.sum, rd.maxSumLeft);
       rd.minSumLeft = min(rd.sum, rd.minSumLeft);
       current += ti;
       if (current > 0ll) {
            current = 0ll;
       }
       if (current < rd.minMiddleSum) {
            rd.minMiddleSum = current;
       }
       // printf("i=%lld sum=%lld mxLeft=%lld minLeft=%lld mid:%lld\n", i, rd.sum, rd.maxSumLeft, rd.minSumLeft, rd.minMiddleSum);
    }
    rd.minSumRight = rd.sum - rd.maxSumLeft;
    rd.maxSumRight = rd.sum - rd.minSumLeft;
    return rd;
}

int masterNode = 0;

int main() {
  long long N = GetN();
  if (N == 1)
    cout << max(0ll, GetTaste(0)) << endl;
  else {
    int number_of_nodes = NumberOfNodes();
    if (MyNodeId() == masterNode) {
        RangeData rd = compute_sum(0, N);
        LL solution = max(0ll, rd.sum - rd.minMiddleSum);
        cout << solution << endl;
        for (int i=0; i < number_of_nodes; i++) {
            if (i==masterNode) {
                continue;
            }   
            PutLL(i, solution);
            Send(i);
        }   
    } else {
        int id = Receive(masterNode); 
        LL solution = GetLL(masterNode);
        // cout << solution << endl;
    }
  }
  
  return 0;
}