Cod sursa(job #188175)

Utilizator za_wolfpalianos cristian za_wolf Data 6 mai 2008 22:35:53
Problema Oo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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;
}
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]);
	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;
}