Cod sursa(job #33432)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 19 martie 2007 13:17:36
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string.h>

#define MAXN 100005

int N, x[MAXN];
int bst[MAXN];
char nok[MAXN];

inline int Max( int a, int b )
{
	return (a > b) ? a : b;
}


int main()
{
	freopen("oo.in", "rt", stdin);
	freopen("oo.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", x + i);
	if (N == 2)
	{
		printf("%d\n", x[1] + x[2]);
		return 0;
	}

	int MAX = -0x3f3f3f3f;
	for (int i = N - 1, prv = N - 2; i != 2; i = i % N + 1, prv = prv % N + 1)
	{
		memset(nok, 0, sizeof(nok));
		for (int j = 0, k = prv; j < 4; j++, k = k % N + 1)
			nok[k] = 1;

		for (int j = 0; j <= N; j++)
			bst[j] = -0x3f3f3f3f;

		if (i % N + 1 == N)
			bst[0] = x[i] + x[i % N + 1];
		else
			bst[i % N + 1] = x[i] + x[i % N + 1];

		for (int j = 1; j < (prv + 4) % N + 1; j++)
			bst[j] = Max( bst[j], bst[j - 1] );

		for (int j = (prv + 4) % N + 1; j <= N; j++)
		{
			if (nok[j] || nok[j - 1])
			{
				bst[j] = bst[j - 1];
				continue;
			}

			bst[j] = Max( bst[j - 1], bst[ Max(j - 3, 0) ] + x[j] + x[j - 1] );
		}

		if (bst[N] > MAX)
			MAX = bst[N];
	}

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

	return 0;
}