Cod sursa(job #380669)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 7 ianuarie 2010 12:27:14
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#define NMAX 100001
int n,v[NMAX],best[NMAX],rez;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
}
inline int max(int a,int b)
{
	return a>b ? a : b;
}
void init(int k)
{
	if (k==1)
		best[1]=v[1]+v[n],best[2]=max(v[1]+v[2],best[1]);
	if (k==2)
		best[1]=0,best[2]=v[1]+v[2];
	if (k==3)
		best[1]=0,best[2]=0;
}
int solve_type(int k)
{
	init(k);
	int i;
	for (i=3; i<=n-3+k; i++)
		best[i]=max(best[i-1],best[i-3]+v[i]+v[i-1]);
	return best[n-3+k];
}
int main()
{
	freopen("oo.in","r",stdin);
	freopen("oo.out","w",stdout);
	read();
	rez=max(solve_type(1),solve_type(2));
	rez=max(rez,solve_type(3));
	printf("%d\n",rez);
	return 0;
}