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
#include "kanapka.h"
#include "message.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<set>
#include<assert.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,n) FOR(i,0,(n)-1)
#define RI(i,n) FOR(i,1,n)
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
bool debug;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;

struct Dane{
  Dane(ll _suma=0, ll _pref=0, ll _val=0) :
    suma(_suma), pref(_pref), val(_val) {}
  ll suma, pref, val;
};

vector<Dane> v;

//przedzial {0 .. N-1}, id jest z przedzialu {0 .. ile_instacji - 1}
//przedzial [lewy, prawy] (wlacznie)
void get_range(ll &lewy, ll &prawy, int id, int ile_instancji, ll N) {
  ll rozmiar = N / ile_instancji;
  ll reszta = N % ile_instancji;
  if (id < reszta) {
    lewy = (rozmiar + 1) * id;
    prawy = lewy + rozmiar;
    return;
  }
  
  lewy = (rozmiar + 1) * reszta + rozmiar * (id - reszta);
  prawy = lewy + rozmiar - 1;
}

void oblicz(ll &suma, ll &pref, ll &val, ll lewy, ll prawy) {
  suma = pref = val = 0;
  ll akt_war = 0;
  FOR(i,lewy,prawy) {
    ll taste = GetTaste(i);
    suma += taste;
    akt_war -= taste;
    if (akt_war < 0) akt_war = 0;
    val = max(val, akt_war);
    pref = max(pref, -suma);
  }
}

int main(int argc, char * argv[]) {
	debug = argc > 1;
  int ile_instancji = NumberOfNodes();
  int id = MyNodeId();
  ll N = GetN();
  ll lewy, prawy;
  get_range(lewy, prawy, id, ile_instancji, N);
  //printf("%lld %lld\n",lewy, prawy);
  ll suma, pref, val;
  oblicz(suma, pref, val, lewy, prawy);
  if (id == 0) {
    v.resize(ile_instancji);
    v[0] = (Dane(suma, pref, val));
    FOR(i,1,ile_instancji-1) {
      int source = Receive(-1);
      ll _suma = GetLL(source);
      ll _pref = GetLL(source);
      ll _val = GetLL(source);
      v[source] = Dane(_suma, _pref, _val);
    }
    
    ll suma_cal = 0;
    ll dupa = 0;
    ll akt_val = 0;
    for (auto dane: v) {
      dupa = max(max(dupa, dane.val), akt_val + dane.pref);
      suma_cal += dane.suma;
      akt_val -= dane.suma;
      if (akt_val < 0) akt_val = 0;
    }
    printf("%lld\n",suma_cal + dupa);
  } else {
    PutLL(0,suma);
    PutLL(0, pref);
    PutLL(0, val);
    Send(0);
  }
	return 0;
}