Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "message.h"
#include "kanapka.h"

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
  /*
    1) Wyznaczany jest rozmiar fragmentu oraz liczba instancji, kt�re maj� bra� udzia� w obliczeniach tak aby ka�da przetwarza�a co najmniej 100k
    2) Ka�da instancja wyznacza i czyta sw�j fragment danych i od razu wylicza max sumy narastaj�co od prawej i sum�.
    3) Wszystkie instancje opr�cz 0 wysy�aj� do 0: sum�, max sumy narastaj�co od prawej
    4) Instacja 0 wyznacza sumy narastaj�co (od obu stron) i max sumy narastaj�cej od prawej na granicach przedzia��w i rozsy�a do pozosta�ych ich warto�ci.
    5) Instancje wyznaczaj� najlepsze wyniki w swoich przedzia�ach i wysy�aj� do 0.
    6) Instancja 0 zbiera odpowiedzi i wypisuje max jako wynik.
  */

  int node = MyNodeId();
  int n = GetN();
  int nn = min(NumberOfNodes(), 1 + n / 100000); // ograniczenie liczby instancji aby ka�da mia�a min. 50-100k (lub ca�o�� dla n < 100k)

  if (node >= nn) return 0; // niepotrzebna instancja

  int s = n / nn;     // d�ugo�� jednej sekcji
  int i0 = node * s; // pozycja pocz�tkowa
  int i1 = (node == nn - 1 ? n - 1 : (node + 1) * s - 1); // pozycja ko�cowa

  int i;

  long long sum;  // suma sekcji
  long long maxr; // max z sum narastaj�co od prawej dla ka�dej pozycji

  long long sum_pop;   // suma poprzednich sekcji
  long long sum_nast;  // suma nast�pnych sekcji
  long long maxr_nast; // maksymalna suma narastaj�co od prawej w nast�pnych sekcjach
  long long *sumr100 = new long long[(i1 - i0 + 1) / 100 + 2];   // sumr100[k] suma narastaj�co od prawej z zakresu (i0 + 100*k)..i1
  long long *maxr100 = new long long[(i1 - i0 + 1) / 100 + 2];   // maxr100[k] maksymalna suma narastaj�ca z zakresu (i0 + 100*k)..i1

  // obliczenie sumy sekcji i maksymalnej sumy narastaj�cej od prawej ----------------------------------------------------
  sum = maxr = GetTaste(i1);
  for (i = i1 - 1; i >= i0; --i) {
    sum += GetTaste(i);
    if (sum > maxr) maxr = sum;
    if((i - i0) % 100 == 0) {
      int k = (i - i0) / 100;
      sumr100[k] = sum;
      maxr100[k] = maxr;
    }
  }

  // wys�anie sum do serwera i odebranie wynikowych sum ---------------------------------------------------------------------
  if (node > 0) {
    PutLL(0, sum);
    PutLL(0, maxr);
    Send(0);
    Receive(0);
    sum_pop = GetLL(0);
    sum_nast = GetLL(0);
    maxr_nast = GetLL(0);
  }
  else if (nn > 1) {  // s� inne instancje -------------------------------------------------------------------------------------
    // serwer odbiera sumy, wyznacza i rozsy�a faktyczne sumy narastaj�co na kra�cach oraz max z sumy od prawej na kra�cach
    long long *tsum = new long long[nn];
    long long *tmaxr = new long long[nn];

    tsum[0] = sum;
    tmaxr[0] = maxr; // w praktyce to niepotrzebne bo nie b�dzie odwo�ania

    for(int odp = 0; odp < nn - 1; ++odp) {  // trzeba zebra� nn - 1 komunikat�w
      int nadawca = Receive(-1);
      tsum[nadawca] = GetLL(nadawca);
      tmaxr[nadawca] = GetLL(nadawca);
    }

    long long *tsum_pop = new long long[nn];   // sumy poprzednich sekcji
    long long *tsum_nast = new long long[nn];  // sumy nast�pnych sekcji
    long long *tmaxr_nast = new long long[nn]; // maksymalna suma narastaj�co od prawej dla kolejnych sekcji

    tsum_pop[0] = 0;
    for (i = 1; i < nn; ++i) {
      tsum_pop[i] = tsum_pop[i - 1] + tsum[i - 1];
    }
    tsum_nast[nn - 1] = tmaxr_nast[nn - 1] = 0;
    for (i = nn - 2; i >= 0; --i) {
      tsum_nast[i] = tsum_nast[i + 1] + tsum[i + 1];
      /* maksymalna suma narastaj�co od prawej (w ca�ej kanapce) dla kolejnych sekcji to maksimum z
           1) maksymalnej sumy w sekcjach "zakolejnych" (czyli kolejnych dla nast�pnej)
           2) sumy "zakolejnych" sekcji i maksymalnej sumy narastaj�cej od prawej wewn�trz nast�pnej sekcji
      */
      tmaxr_nast[i] = max(tmaxr_nast[i + 1], tsum_nast[i + 1] + tmaxr[i + 1]);
    }

    // wys�a� dane do pozosta�ych instancji
    for (i = 1; i < nn; ++ i) {
      PutLL(i, tsum_pop[i]);
      PutLL(i, tsum_nast[i]);
      PutLL(i, tmaxr_nast[i]);
      Send(i);
    }

    // ustawi� warto�ci dla serwera
    sum_pop = 0;
    sum_nast = tsum_nast[0];
    maxr_nast = tmaxr_nast[0];
  }
  else {  // serwer dzia�a sam --------------------------------------------------------------------------
    sum_pop = sum_nast = maxr_nast = 0;
  }

  // obliczenie najlepszego wyniku w sekcji -------------------------------------------------------------
  int imaxr0;  // pocz�tkowa pozycja od kt�rej b�d� trzymane dane w maxri
  long long maxri[100 + 1]; // maxr_i[i] - maksymalna suma narastaj�co w sekcji od pozycji imaxr0 + i (+1 na stra�nika)
  long long wynik = 0;
  sum = 0;
  for (i = i0; i <= i1; ++i) {
    if ((i - i0) % 100 == 0) {   // obliczenie maksymalnych sum narastaj�co w sekcji od prawej dla kolejnych 100 pozycji
      int k = (i - i0) / 100;
      imaxr0 = i;
      maxr = i + 100 > i1 ? 0 : maxr100[k + 1];
      long long sumr = i + 100 > i1 ? 0 : sumr100[k + 1];
      int j1 = min(i1, i + 100 - 1); //i + 99 lub ostatni element
      maxri[j1 + 1 - imaxr0] = 0; // stra�nik
      for (int j = j1; j >= imaxr0; --j) {
        sumr += GetTaste(j);
        if (sumr > maxr) maxr = sumr;
        maxri[j - imaxr0] = maxr;
      }
    }
    sum += GetTaste(i);
    /* wynik przy za�o�eniu, �e z przodu gryziemy 0..i jest r�wny:
         suma poprzednich sekcji (0..i0-1) PLUS
         suma narastaj�co z aktualnej sekcji (i0..i) PLUS
         maksimum z:
           1) 0 - to jest przypadek, �e z prawej nic si� nie da ugry��
           2) sumy wszystkich kolejnych sekcji (i1+1..n-1) oraz maksymalnej sumy narastaj�co od prawej w bie��cej sekcji
              za pozycj� i (i+1..i1) - to jest przypadek gdzie od prawej ugryziemy do miejsca w bie��cej sekcji
           3) maksymalnej sumy narastaj�co od prawej do uzyskania gdzie� w kolejnych sekcjach (maxr_nast) - to jest przypadek
              gdzie od prawej ugryziemy do miejsca, kt�re jest w kolejnych sekcjach
    */
    long long w = sum_pop + sum + max(0LL, max(sum_nast + maxri[i + 1 - imaxr0], maxr_nast));  // dla i == min(i1, imaxr0 + 100) b�dzie odwo�anie do stra�nika w maxr
    if (w > wynik) wynik = w;
  }

  if (node > 0) { // wys�anie wyniku do serwera --------------------------------------------------------------
    PutLL(0, wynik);
    Send(0);
  }
  else { // odebranie odpowiedzi, wyznaczenie i wypisanie najlepszego wyniku
    for(int odp = 0; odp < nn - 1; ++odp) {
      int nadawca = Receive(-1);
      long long w = GetLL(nadawca);
      if (w > wynik) wynik = w;
    }
    cout << wynik << endl;
  }

  return 0;
}