Cod sursa(job #188179)

Utilizator za_wolfpalianos cristian za_wolf Data 6 mai 2008 22:50:13
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<string.h>
#define  NMAX 110000
long x[NMAX],y[NMAX],rez,z[NMAX],i,j,n,m,k,l,a,s;
long max(long a, long b)
{
	if (a>b)
		return a;
	return b;
}
void solve()
{
	y[1]=x[1]+x[2];
	z[2]=x[1]+x[2];
	y[2]=x[2]+x[3];
	y[2]=max(y[2],y[1]);

	for (i=3;i<n;i++)
	{
		if (i!=n-1)
		y[i]=max(z[i-2],y[i-3])+x[i]+x[i+1];
		y[i]=max(y[i],y[i-1]);
		z[i]=max(z[i-3],y[i-4])+x[i-1]+x[i];
		z[i]=max(z[i],z[i-1]);

		rez=max(rez,z[i]);
		rez=max(rez,y[i]);
	}
	memset(y,0,sizeof(y));
	memset(z,0,sizeof(z));

}
void mut()
{
	a=x[n];
	for (i=n;i>=2;i--)
		x[i]=x[i-1];
	x[1]=a;
}

int main()
{
	freopen("oo.in","r",stdin);
	freopen("oo.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);
	solve();
	mut();
	solve();
	mut();
	solve();
/*	y[1]=x[1]+x[2];
	z[2]=x[1]+x[2];
	y[2]=x[2]+x[3];
	y[2]=max(y[2],y[1]);

	for (i=3;i<n;i++)
	{
		if (i!=n-1)
		y[i]=max(z[i-2],y[i-3])+x[i]+x[i+1];
		y[i]=max(y[i],y[i-1]);
		z[i]=max(z[i-3],y[i-4])+x[i-1]+x[i];
		z[i]=max(z[i],z[i-1]);

		rez=max(rez,z[i]);
		rez=max(rez,y[i]);
	}
	memset(y,0,sizeof(y));
	memset(z,0,sizeof(z));

	y[2]=x[2]+x[3];
	z[3]=x[2]+x[3];
	y[3]=x[3]+x[4];
	y[3]=max(y[3],y[2]);
	x[n+1]=x[1];
	for (i=4;i<n;i++)
	{
		if (i!=n-1)
			y[i]=max(z[i-2],y[i-3])+x[i]+x[i+1];
		y[i]=max(y[i],y[i-1]);
		z[i]=max(z[i-3],y[i-4])+x[i-1]+x[i];
		z[i]=max(z[i],z[i-1]);

		rez=max(rez,z[i]);
		if (i!=n)
		rez=max(rez,y[i]);
	}
*/

	printf("%ld\n",rez);

	return 0;
}