Cod sursa(job #2070771)

Utilizator WebDesignbyTMGhiorghiu Ioan-Viorel WebDesignbyTM Data 19 noiembrie 2017 21:48:12
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#define DM 100001
#include <cstdio>
#include <fstream>
using namespace std;

ifstream fi ("oo.in");
ofstream fo ("oo.out");
int n, dp[DM], v[DM], x[DM], mx;//n - nr elemente; v - elementele; dp - summax pana la i; mx - raspuns

int main()
{
	//citire
	fi >> n;
	for (int i = 1; i <= n; ++i)
		fi >> v[i];
	//initializare
	dp[1] = x[1] = v[n] + v[1];
	x[2] = v[2] + v[1], x[3] = v[3] + v[2];
	dp[2] = max(dp[1], x[2]);
	dp[3] = max(x[3], dp[2]);
	mx = max(dp[1], max(dp[2], dp[3]));
	//dinamica 1
	for (int i = 4; i < n - 1; ++i)
	{
		x[i] = dp[i-3] + v[i] + v[i-1];
		dp[i] = max(dp[i-1], x[i]);
	}
	mx = max(mx, dp[n-2]);
	//dinamica 2
	for (int i = 0; i <= n; ++i)
		dp[i] = x[i] = 0;
	x[2] = dp[2] = v[2] + v[1];
	x[3] = v[3] + v[2];
	dp[3] = max(x[3], dp[2]);
	for (int i = 4; i < n; ++i)
	{
		x[i] = dp[i-3] + v[i] + v[i-1];
		dp[i] = max(dp[i-1], x[i]);
	}
	mx = max(mx, dp[n-1]);
	//dinamica 3
	for (int i = 0; i <= n; ++i)
		dp[i] = x[i] = 0;
	dp[3] = x[3] = v[3] + v[2];
	for (int i = 4; i <= n; ++i)
	{
		x[i] = dp[i-3] + v[i] + v[i-1];
		dp[i] = max(dp[i-1], x[i]);
	}
	mx = max(mx, dp[n]);
	fo << mx;
	return 0;
}