#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;
}