Cod sursa(job #890157)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 24 februarie 2013 21:28:44
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb

#include <cstdio>

const int MAX_N(100002);

int n, result;
int v [MAX_N];
int dp [MAX_N];

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

inline void read (void)
{
	std::freopen("oo.in","r",stdin);
	std::scanf("%d",&n);
	for (int i = 1 ; i <= n ; ++i)
		std::scanf("%d",&v[i]);
	v[n + 1] = v[1];
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("oo.out","w",stdout);
	std::printf("%d\n",result);
	std::fclose(stdout);
}

inline void dynamic (int start, int end)
{
	dp[start - 2] = 0;
	dp[start - 1] = v[start - 2] + v[start - 1];
	for (int i(start) ; i <= end ; ++i)
		dp[i] = max(dp[i - 1],dp[i - 3] + v[i - 1] + v[i]);
	result = max(result,dp[end]);
}

int main (void)
{
	read();
	for (int i(0) ; i < 3 ; ++i)
		dynamic(3 + i,n - 1 + i);
	print();
	return 0;
}