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


int suma(long long sumarr[], int from, int too)
{
  long long ans = 0;
  for (int i=from; i<=too; i++){
    ans+=sumarr[i];
  }
  return ans;
}

int main() {
  long long N = GetN();
  int nodes = NumberOfNodes();
  long long sum = 0ll;
  long long MIN = -10000000000ll, MAX = 10000000000ll;
  long long prefix_max = 0ll;
  long long prefix_min = 0ll;
  long long suffix_min = 0ll;
  long long inner_min = 0;
  long long poczatek = (MyNodeId() * N) / nodes;
  long long koniec = ((MyNodeId() + 1) * N) / nodes;

  /*if (MyNodeId() == 0) {
    for (int i=0; i<N; i++){
      cout << GetTaste(i) << " ";
    }
    cout << endl;
  }*/
  // Faza pierwsza.
  long long inner = 0;
  for (long long i = poczatek; i < koniec; ++i) {
      long long taste = GetTaste(i);

      sum = sum + taste;
      prefix_max = max(prefix_max, sum);
      prefix_min = min(prefix_min, sum);

      inner = min(0ll, inner + taste);
      inner_min = min(inner_min, inner);
  }

  suffix_min = sum - prefix_max;
//cout <<"Node "<<MyNodeId()<<" from: "<<poczatek<<" to: "<<koniec<<" sum: "<<sum<<" prefix_min: "<<prefix_min<<" suffix_min: "<<suffix_min<<" inner_min: "<<inner_min<<endl;
  if (MyNodeId() > 0) {
        PutLL(0, sum);
        PutLL(0, prefix_min);
        PutLL(0, suffix_min);
        PutLL(0, inner_min);

        //cout << "Node "+MyNodeId()" wysyla dane : from: "+poczatek <<", to: "+koniec <<",sum : " + sum << ", pmin : " + prefix_min << ", smin: " + suffix_min <<endl;
        Send(0);
  } else {
    long long sumarr[nodes];
    long long prefixes[nodes];
    long long suffixes[nodes];
    long long inners[nodes];

    sumarr[0] = sum;
    prefixes[0] = prefix_min;
    suffixes[0] = suffix_min;
    inners[0] = inner_min;

    long long all = sumarr[0];

    for (int i=1; i<nodes; ++i){
      int instancja = Receive(-1);
      sumarr[instancja] = GetLL(instancja);
      prefixes[instancja] = GetLL(instancja);
      suffixes[instancja] = GetLL(instancja);
      inners[instancja] = GetLL(instancja);
      all += sumarr[instancja];
    }
    long long worse = MAX;

    for (int a = 0; a<nodes; a++){
      for (int b = a + 1; b<nodes; b++){
        worse = min(worse, suffixes[a] + suma(sumarr, a+1, b-1) + prefixes[b]);
      }
      worse = min(worse, inners[a]);
      worse = min(worse, prefixes[a]);
      worse = min(worse, suffixes[a]);
    }

    worse = min(worse, suffixes[nodes-1]);

    cout << (all - worse) << endl;
  }

  return 0;
}