Cod sursa(job #33212)

Utilizator gcosminGheorghe Cosmin gcosmin Data 18 martie 2007 23:41:38
Problema Oo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <string.h>
#define max(a,b) ( (a) > (b) ? (a) : (b) )
#define NMAX 10010
#define INF (1 << ( sizeof(int) * 8 - 2) )
int n;
int a[NMAX];
int cu[NMAX];
int fa[NMAX];

int create(int beg, int end)
{
	int i;
	for (i = beg; i <= end; i++)
	{
		cu[i] = a[i-1] + a[i] + fa[i - 2];
		fa[i] = max(fa[i-1], cu[i-1]);
	}

return 0;
}
int main()
{
	int i;
	int mx = -INF;
	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);

	scanf("%d", &n);

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

	// cazu 1.... iau n si 1 si merg pana la n - 2
	memset(cu, 0, sizeof(cu));
	memset(fa, 0, sizeof(fa));
	cu[1] = a[1] + a[n];
	fa[2] = cu[1];
	create(3, n - 2);
	mx = max(mx, max(cu[n-2], fa[n-2]));

	// cazu 2.... iau 1 si 2 si merg pana la n - 1
	memset(cu, 0, sizeof(cu));
	memset(fa, 0, sizeof(fa));
	cu[2] = a[1] + a[2];
	fa[3] = cu[2];
	create(4, n - 1);
	mx = max(mx, max(cu[n-1], fa[n-1]));

	// cazu 3.... iau 2 si 3 si merg pana la n
	memset(cu, 0, sizeof(cu));
	memset(fa, 0, sizeof(fa));
	cu[3] = a[2] + a[3];
	fa[4] = cu[3];
	//cu[4] = a[4] + cu[2];
	create(5, n);
	mx = max(mx, max(cu[n], fa[n]));

	printf("%d\n", mx);

fclose(stdin);
fclose(stdout);
return 0;
}