Cod sursa(job #32849)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 18 martie 2007 16:42:24
Problema Oo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#define FIN "oo.in"
#define FOUT "oo.out"
#define MAX 10001

inline long max (long x, long y) {
	return ( x>y ) ? x : y;
}

long N, A[MAX], V[MAX];
// V[x] = maximul pana la pozitia x 

inline long elem(long x) {
	if ( x<0 ) x+=N;
	return (x) % N;
}

long solve() {
	if ( N==2 ) 
		return A[0] + A[1];
	if ( N==3 ) 
		return max(A[0]+A[1],A[1]+A[2]);

	long ret = 0,i;
	// unim pe primul cu al doilea.
	V[N-1] = 0, V[0] = 0;
	V[1] = A[0] + A[1];
	for (i=3; i<N-1; ++i) 
		V[i] = max(V[i-1], V[i-3] + A[i] + A[i-1]); // nu luam pe i sau luam pe i unit cu i-1
	if ( ret<V[N-2] ) 
		ret = V[N-2];

	//unim pe ultimul cu primul.
	V[N-1] = V[N-2] = 0;
	V[0] = A[0] + A[N-1];
	for (i=2; i<N-2; ++i) 
		V[i] = max(V[i-1], V[elem(i-3)]+ A[i]+A[i-1]);
	if ( ret<V[N-3] )
		ret = V[N-3];

	//unim pe al doilea cu al treilea...
	V[1] = V[0] = 0;
	V[3] = A[1] + A[2];
	for (i=4; (i<N && i>3); i=elem(i+1)) 
		V[i] = max(V[elem(i-1)], V[elem(i-3)] + A[i] + A[elem(i-1)]);
	if ( ret<V[N-1] ) 
		ret = V[N-1];
	
	return ret;
}

int main() {
	long i;
	freopen(FIN, "r", stdin);
	scanf("%ld", &N);
	for (i=0; i<N; ++i)
		scanf("%ld", A+i);
	fclose(stdin);


	freopen(FOUT, "w", stdout);
	printf("%ld\n", solve());
	fclose(stdout);
	return 0;
}