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
#include<bits/stdc++.h>
#include"kanapka.h"
#include"message.h"
using namespace std;
typedef long long int lld;

int SIZE;
const int PACK = 250;
int RATIO;

void Core(void){
	vector<lld> a,b,c,d;

	for(int i=1;i<NumberOfNodes();i++){
		Receive(i);

		for(int j=0;j<PACK;j++){
			a.push_back(GetLL(i));
			b.push_back(GetLL(i));
			c.push_back(GetLL(i));
			d.push_back(GetLL(i));
		}
	}

	int n = a.size();

	lld sum = 0;
	for(lld& i : a)
		sum += i;

	lld res = 0;

	for(int i=0;i<n;i++)
		res = max(res, sum-a[i]+d[i]);

	vector<lld> x(n), y(n);
	vector<lld> t(n);
	x[0] = max(0ll, b[0]);
	t[0] = a[0];

	for(int i=1;i<n;i++){
		x[i] = max(x[i-1] , b[i]+t[i-1]);
		t[i] = t[i-1]+a[i];
	}

	y[n-1] = max(0ll, c[n-1]);
	t[n-1] = a[n-1];

	for(int i=n-2;i>=0;i--){
		y[i] = max(y[i+1] , c[i]+t[i+1]);
		t[i] = t[i+1]+a[i];
	}

	for(int i=0;i<n-1;i++)
		res = max(res, x[i]+y[i+1]);
	res = max(res,x[n-1]);
	res = max(res,y[0]);

	cout << res << "\n";
}

lld GetNr(int a){
	return (a < GetN() ? GetTaste(a) : 0);
}

void calc(int a, int b){
	lld sum;
	lld res = 0;
	vector<lld> x(b-a), y(b-a);

	sum = GetNr(a);
	x[0] = GetNr(a);
	for(int i=a+1;i<b;i++){
		sum += GetNr(i);
		x[i-a] = max(x[i-a-1], sum);
	}

	sum = GetNr(b-1);
	x[b-a-1] = GetNr(b-1);
	for(int i=b-2;i>=a;i--){
		sum += GetNr(i);
		y[i-a] = max(y[i-a+1], sum);
	}

	for(int i=0;i<b-a;i++)
		res = max(res, x[i]+y[i+1]);
	res = max(res, x[0]);
	res = max(res, y[b-a-1]);

	PutLL(0, sum);
	PutLL(0, x[b-a-1]);
	PutLL(0, y[0]);
	PutLL(0, res);
}

void Help(void){
	int nr = MyNodeId()-1;
	int a = nr*PACK, b=(nr+1)*PACK;

	for(int i=a;i<b;i++)
		calc(i*RATIO,(i+1)*RATIO);

	Send(0);
}

int main(void){
	SIZE = ((2*GetN())/NumberOfNodes())+10;
	RATIO = SIZE/PACK+1;

	if(MyNodeId() == 0)
		Core();
	else
		Help();

	return 0;
}