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
#include <iostream>
#include <algorithm>
using namespace std;

#include "message.h"
#include "kanapka.h"

typedef long long LL;

const int MASTER = 0;
const int MAX_NODES = 110;
const LL INF = 999999999999999999LL;


LL sums[MAX_NODES];
LL maxSums[MAX_NODES];

int getNumWorkers() {
    return min((int)GetN(), NumberOfNodes() - 1);
}


int main() {
  if(MyNodeId() == MASTER) {
    LL n = GetN();
    LL sumAll = 0;
    
    int numWorkers = getNumWorkers(); 
    LL len = (n + numWorkers - 1) / numWorkers;
    for(int i=1; i <= numWorkers; i++) {
      PutLL(i, (i-1)*len); 
      PutLL(i, len);
      Send(i);
    }

    for(int i=1; i <= numWorkers; i++) {
      Receive(i);
      sums[i] = GetLL(i);
      maxSums[i] = GetLL(i);
      sumAll += sums[i]; 
    }

    LL sumPref = 0;
    LL maxSumPref = 0;
    for(int i=1; i <= numWorkers; i++) {
      PutLL(i, sumAll);
      PutLL(i, sumPref);
      PutLL(i, maxSumPref);
      Send(i);
      maxSumPref = max(maxSumPref, sumPref + maxSums[i]);
      sumPref += sums[i];
    }

    LL result = -INF; 
    for(int i=1; i <= numWorkers; i++) {
      Receive(i);
      result = max(result, GetLL(i));
    }

    cout << result << endl;
  } else if(MyNodeId() <= getNumWorkers()) {
    Receive(MASTER); 
    LL offset = GetLL(MASTER);
    LL len = GetLL(MASTER);
    LL sumAll = 0, maxSum = 0;
    LL n = GetN();
    LL limit = offset + len;
    if(limit > n) limit = n;
    for(LL i=offset; i < limit; i++) {
      sumAll += GetTaste(i); 
      maxSum = max(maxSum, sumAll);
    }
    PutLL(MASTER, sumAll);
    PutLL(MASTER, maxSum);
    Send(MASTER);

    Receive(MASTER);
    sumAll = GetLL(MASTER);
    LL sumPref = GetLL(MASTER);
    LL maxSumPref = GetLL(MASTER);
    LL result = -INF;
    for(LL i=offset; i < limit; i++) {
      sumPref += GetTaste(i);
      maxSumPref = max(maxSumPref, sumPref);
      result = max(result, sumAll - sumPref + maxSumPref);
    }
    PutLL(MASTER, result);
    Send(MASTER);
  }
  return 0;
}