Cod sursa(job #35058)

Utilizator peanutzAndrei Homorodean peanutz Data 21 martie 2007 19:33:12
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <memory.h>

#define NMAX 100010

int a[NMAX];
long n;
long rez;

inline long max(long a, long b)
{
	if(a > b)
		return a;
	return b;
}

long unu()
{
	long sol[NMAX];
	long i, j, curent, maxlocal;

	maxlocal = curent = 0;
	memset(sol, 0, sizeof(sol));

	//sol[2] = a[1] + a[2];

	for(i = 5; i < n; ++i)
	{
		curent = 0;

		for(j = 2; j < 5; ++j)
		{
			if(i-j > 1)
				curent = max(a[i-1]+a[i]+sol[i-j], curent);
		}

		sol[i] = curent;

		if(maxlocal < curent)
			maxlocal = curent;
	}

	return maxlocal+a[n]+a[n-1];
}

long doi()
{
	int i, j, curent, maxlocal;
	int sol[NMAX];

	memset(sol, 0, sizeof(sol));
	maxlocal = 0;


	for(i = 4; i < n-1; ++i)
	{
		curent = 0;

		for(j = 2; j < 5; ++j)
		{
			if(i-j > 1)
				curent = max(a[i-1]+a[i]+sol[i-j], curent);
		}

		sol[i] = curent;

		if(maxlocal < curent)
			maxlocal = curent;
	}

	return maxlocal+a[1]+a[n];
}


long trei()
{
	int i, j, maxlocal, curent;
	int sol[NMAX];

	maxlocal = 0;

	memset(sol, 0, sizeof(sol));


	for(i = 4; i < n-2; ++i)
	{
		curent = 0;

		for(j = 3; j < 5; ++j)
		{
			if(i-j > 1)
				curent = max(a[i-1]+a[i]+sol[i-j], curent);
		}

		sol[i] = curent;

		if(maxlocal < curent)
			maxlocal = curent;

	}

	return maxlocal+a[n]+a[n-1];
}

int main()
{
	long i;

	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);

	scanf("%ld\n", &n);

	for(i = 1; i <= n; ++i)
	{
		scanf("%d ", &a[i]);
	}

	rez = max(rez, unu());
	rez = max(rez, doi());
	rez = max(rez, trei());

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


	fclose(stdin);
	fclose(stdout);

	return 0;
}