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

typedef long long ll;

int main() {
  // This node will cover the range [beg, end).
  ll beg = (GetN() * MyNodeId()) / NumberOfNodes();
  ll end = (GetN() * (MyNodeId() + 1)) / NumberOfNodes();
  // Instead of looking for the tastiest prefix and suffix, we look for the
  // least tasty interior.
  ll sum = 0LL;  // Sum of all elements in the range
  ll prefix = 0LL;  // The least tasty prefix of the range
  ll interior = 0LL;  // The least tasty interior within the range
  ll suffix = 0LL;  // The least tasty suffix of the range.
  for (ll i = beg; i < end; ++i) {
    sum += GetTaste(i);
    suffix += GetTaste(i);
    if (suffix > 0LL) suffix = 0LL;
    interior = (suffix < interior) ? suffix : interior;
    prefix = (sum < prefix) ? sum : prefix;
  }
  // Send the four numbers to the master node.
  PutLL(0, sum);
  PutLL(0, prefix);
  PutLL(0, interior);
  PutLL(0, suffix);
  Send(0);
  if (MyNodeId() == 0) {
    // Gather all the information from all the nodes.
    ll all_sums[100];
    ll all_prefixes[100];
    ll all_interiors[100];
    ll all_suffixes[100];
    for (int i = 0; i < NumberOfNodes(); ++i) {
      int node = Receive(-1);
      all_sums[node] = GetLL(node);
      all_prefixes[node] = GetLL(node);
      all_interiors[node] = GetLL(node);
      all_suffixes[node] = GetLL(node);
    }
    // Now we do almost the same calculation to find the best overall interior.
    sum = interior = suffix = 0LL;
    for (int i = 0; i < NumberOfNodes(); ++i) {
      // The interior of the i-th node is a candidate for the worst interior.
      interior = (interior < all_interiors[i]) ? interior : all_interiors[i];
      // Also, something from the previous nodes, plus a prefix of this node.
      interior = (interior < suffix + all_prefixes[i])
                     ? interior
                     : suffix + all_prefixes[i];
      // The suffix is either just contained in this node, or it's all of this
      // node and a suffix of the rest.
      suffix = (all_suffixes[i] < all_sums[i] + suffix) ? all_suffixes[i]
                                                        : all_sums[i] + suffix;
      // The total sum is just accumulating.
      sum += all_sums[i];
    }
    // And the answer is the total taste of the sandwich minus the worst
    // interior.
    printf("%lld\n", sum - interior);
  }
  return 0;
}