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

using LL = long long;

struct S {
  S():
      minPrefix(0), 
      minSuffix(0), 
      minInfix(0), 
      total(0){}
  S(LL x):
      minPrefix(min(0ll, x)), 
      minSuffix(min(0ll, x)), 
      minInfix(min(0ll, x)), 
      total(x){}

  S(LL minPrefix, LL minSuffix, LL minInfix, LL total):
      minPrefix(minPrefix), 
      minSuffix(minSuffix), 
      minInfix(minInfix), 
      total(total){}

  S append(S const &s) const {
    return S(
      min(minPrefix, total + s.minPrefix), // minPrefix
      min(minSuffix + s.total, s.minSuffix), // minSuffix
      min(min(minInfix, s.minInfix), minSuffix + s.minPrefix), // minInfix 
      total + s.total
    );
  }
  LL minPrefix;
  LL minSuffix;
  LL minInfix;
  LL total;
};
int main(){
  int numberOfNodes = NumberOfNodes();
  int myNodeId = MyNodeId();

  LL n = GetN();
  LL begin = ((LL) myNodeId * n) / numberOfNodes;
  LL end = ((LL) (myNodeId + 1) * n) / numberOfNodes;
  
  S s;
  for(LL i = begin; i < end; i++) {
    s = s.append(S(GetTaste(i)));
  }
  if(myNodeId > 0) {
    PutLL(0, s.minPrefix);
    PutLL(0, s.minSuffix);
    PutLL(0, s.minInfix);
    PutLL(0, s.total);
    Send(0);
  } else {
    for (int nodeId = 1; nodeId < numberOfNodes; ++nodeId) {
      Receive(nodeId);
      LL minPrefix = GetLL(nodeId);
      LL minSuffix = GetLL(nodeId);
      LL minInfix = GetLL(nodeId);
      LL total = GetLL(nodeId);
      s = s.append(S(minPrefix, minSuffix, minInfix, total));
    }
    cout << s.total - s.minInfix << endl;
  }
  return 0;
}