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
//Daniel Grzegorzewski
#include <bits/stdc++.h>
#include "message.h"
#include "kanapka.h"

#define MP make_pair
#define PB push_back
#define ST first
#define ND second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0);
}

VI pref, suf;
int res = -(int)1e18, sum, maxi, lewy, prawy;

int max(int x, int y)
{
	if (x < y)
		return y;
	return x;
}

#undef int
int main()
{
#define int long long
    init_ios();
    int n = GetN();
    int ile = NumberOfNodes();
    int id = MyNodeId();
    if (ile >= n && id > 0)
    	return 0;
    if (ile >= n && id == 0) {
    	int tmp = 0;
    	suf.PB(tmp);
    	for (int i = n-1; i >= 0; --i) {
    		tmp += GetTaste(i);
    		suf.PB(max(suf.back(), tmp));
    	}
    	tmp = 0;
    	pref.PB(tmp);
    	for (int i = 0; i < n; ++i) {
    		tmp += GetTaste(i);
    		pref.PB(max(pref.back(), tmp));
    		res = max(res, pref.back()+suf[n-1-i]);
    	}
    	cout<<res<<"\n";
    	return 0;
    }
    int pocz = (id*n)/ile, kon = ((id+1)*n)/ile, tmp = 0;
    suf.PB(tmp);
    for (int i = kon-1; i >= pocz; --i) {
    	tmp += GetTaste(i);
    	suf.PB(max(suf.back(), tmp));
    }
    sum = tmp;
    tmp = 0;
    pref.PB(tmp);
    res = suf[kon-pocz];
    for (int i = pocz; i < kon; ++i) {
    	tmp += GetTaste(i);
    	pref.PB(max(pref.back(), tmp));
    	res = max(res, pref.back()+suf[kon-1-i]);
    }
    if (id == ile-1) {
    	PutLL(id-1, sum);
    	Send(id-1);
    }
    else if (id < ile-1) {
    	Receive(id+1);
    	prawy = GetLL(id+1);
    	if (id > 0) {
    		PutLL(id-1, sum+prawy);
    		Send(id-1);
    	}
    }
    if (id == 0) {
    	maxi = res+prawy;
    	PutLL(id+1, maxi);
    	PutLL(id+1, sum);
    	Send(id+1);
    }
    else {
    	Receive(id-1);
    	maxi = GetLL(id-1);
    	lewy = GetLL(id-1);
    	maxi = max(maxi, lewy+prawy+res);
    	if (id < ile-1) {
    		PutLL(id+1, maxi);
    		PutLL(id+1, sum+lewy);
    		Send(id+1);
    	}
    	if (id == ile-1) {
    		cout<<max(0, maxi)<<"\n";
    		return 0;
    	}
    }
}