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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*PA2015 etap0 Kanapka*/
#include"kanapka.h"
#include"message.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  int iloscKompow = min(static_cast<long long>(NumberOfNodes()), GetN());
  if(MyNodeId() >= iloscKompow)
    return 0;

  long long indeksOd =
      GetN() % iloscKompow == 0 ? (GetN() / iloscKompow) * MyNodeId() :
        MyNodeId() < GetN() % iloscKompow ? (GetN() / iloscKompow + 1) * MyNodeId() :
          (GetN() / iloscKompow + 1) * (GetN() % iloscKompow) +
          (GetN() / iloscKompow) * (MyNodeId() - GetN() % iloscKompow);
  long long indeksDo = indeksOd +
      (MyNodeId() < GetN() % iloscKompow ? GetN() / iloscKompow : GetN() / iloscKompow - 1);

  long long smak;
  long long suma = 0LL;
  long long Mi = 0LL, Mp = indeksOd, M = 0LL, Ma = -1LL, Mb = -1LL;
  long long Pi = 0LL, P = 0LL, Pr = indeksOd - 1;
  long long Si = 0LL, S = 0LL, Ss = indeksDo + 1;
  long long N1 = 0LL;
  long long N2 = 0LL;
  for(long long i = indeksOd; i <= indeksDo; ++i) {
    smak = GetTaste(i);
    suma += smak;
    Mi += smak;
    if(Mi > 0LL) {
      Mi = 0;
      Mp = i + 1;
    } else if(Mi < M) {
        M = Mi;
        Ma = Mp;
        Mb = i;
      }
    Pi += smak;
    if(Pi < 0LL && Pi < P) {
      P = Pi;
      Pr = i;
    }
  }
  if(Ma < 0LL)
    N1 = suma;
  else {
    for(long long i = indeksDo; i >= indeksOd; --i) {
      Si += GetTaste(i);
      if(Si < 0LL && Si < S) {
        S = Si;
        Ss = i;
      }
    }
    if(Pr < Ma)
      for(long long i = Pr + 1; i < Ma; ++i)
        N1 += GetTaste(i);
    else {
      N1 = P - M;
      P = 0LL;
    }
    if(Ss > Mb)
      for(long long i = Mb + 1; i < Ss; ++i)
        N2 += GetTaste(i);
    else {
      N2 = S - M;
      S = 0LL;
    }
  }

  if(MyNodeId() == 0) {
    vector<long long> zbiorczo(iloscKompow * 5);
    zbiorczo[0] = P;
    zbiorczo[1] = N1;
    zbiorczo[2] = M;
    zbiorczo[3] = N2;
    zbiorczo[4] = S;


//    cout << P << " " << N1 << " " << M << " " << N2 << " " << S << endl;

    for(int i = 0; i < (iloscKompow - 1) * 5; ++i) {
      int komp = Receive(-1);
      int indeks = komp * 5 + GetInt(komp);
      zbiorczo[indeks] = GetLL(komp);
    }
    suma = 0LL;
    Mi = 0LL; Mp = 0; M = 0LL; Ma = -1LL; Mb = -1LL;
    Pi = 0LL; P = 0LL;
    Si = 0LL; S = 0LL;
    for(int i = 0; i < iloscKompow * 5; ++i) {
      smak = zbiorczo[i];
      suma += smak;
      Mi += smak;
      if(Mi > 0LL) {
        Mi = 0;
        Mp = i + 1;
      } else if(Mi < M) {
          M = Mi;
          Ma = Mp;
          Mb = i;
        }
    }
    cout << suma - M << endl;
  } else {
    PutInt(0, 0);
    PutLL(0, P);
    Send(0);
    PutInt(0, 1);
    PutLL(0, N1);
    Send(0);
    PutInt(0, 2);
    PutLL(0, M);
    Send(0);
    PutInt(0, 3);
    PutLL(0, N2);
    Send(0);
    PutInt(0, 4);
    PutLL(0, S);
    Send(0);
  }
  return 0;
}