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
//Dominik Klemba
#include "message.h"
#include "maklib.h"
#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

long long centrum(const unsigned);
void policz(const unsigned, const unsigned);
long long zwyczajny(const unsigned);

int main() {
  ios_base::sync_with_stdio(false);
  const unsigned liczba_komputerow = NumberOfNodes(), moj_numer = MyNodeId(), rozmiar = Size();
  if(rozmiar <= 750000) {
    if(moj_numer != 0)
     return 0;
    const long long odpowiedz = zwyczajny(rozmiar);
    cout << odpowiedz << '\n';
    return 0;
   }
  if(moj_numer == 0) {
    const long long odpowiedz = centrum(liczba_komputerow);
    cout << odpowiedz << '\n';
   }
  else {
    const unsigned partia = (rozmiar/(liczba_komputerow-1));
    const unsigned p = partia*(moj_numer-1) + 1;
    const unsigned q = (moj_numer + 1 == liczba_komputerow) ? rozmiar + 1 : p + partia;
    policz(p,q);
   }
  return 0;
 }

long long centrum(const unsigned liczba_komputerow) {
  typedef tuple<long long, long long, long long, long long> dane_fragmentu;
  vector<dane_fragmentu> rozwiazania(liczba_komputerow - 1);
  for(unsigned i = 1; i < liczba_komputerow; ++i) {
    const unsigned pobrano_od = Receive(-1);
    get<0>(rozwiazania[pobrano_od-1]) = GetLL(pobrano_od);
    get<1>(rozwiazania[pobrano_od-1]) = GetLL(pobrano_od);
    get<2>(rozwiazania[pobrano_od-1]) = GetLL(pobrano_od);
    get<3>(rozwiazania[pobrano_od-1]) = GetLL(pobrano_od);
   }

  long long maks = 0, suma = 0;
  for(auto& x : rozwiazania) {
    maks = max(maks, suma + get<0>(x));
    suma += get<3>(x);
    suma = max(suma, get<2>(x));
    maks = max(maks, suma);
    maks = max(maks, get<1>(x));
   }
  return maks;
 }

void policz(const unsigned p, const unsigned q) { // [)
  long long lmaks = 0, maks = 0, suma = 0, cala_suma = 0;
  for(unsigned i = p; i < q; ++i) {
    const int aktualny = ElementAt(i);
    cala_suma += aktualny;
    lmaks = max(lmaks, cala_suma);
    suma += aktualny;
    suma = max(0LL, suma);
    maks = max(suma, maks);
   }
  PutLL(0, lmaks);
  PutLL(0, maks);
  PutLL(0, suma);
  PutLL(0, cala_suma);
  Send(0);
 }

long long zwyczajny(const unsigned q) {
  long long suma = 0, maks = 0;
  for(unsigned i = 1; i <= q; ++i) {
    suma = max(suma + ElementAt(i), 0LL);
    maks = max(maks, suma);
   }
  return maks;
 }