Cod sursa(job #3121695)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 14 aprilie 2023 20:36:25
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& v)
{
	int n = v.size(), dp[n];
	if(n == 1)
		return 0;
	memset(dp, 0, sizeof(dp));
	dp[1] = v[0] + v[1];
	
	for(int i = 2;i < n;++i)
	{
		int add = 0;
		if(i >= 3)
			add = dp[i - 3];
		dp[i] = max(dp[i - 1], v[i] + v[i - 1] + add);
	}
	return dp[n - 1];
}

int main() {
	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i = 0;i < n;++i)
		cin >> v[i];
	vector<int> t1, t2;
	for(int i = 0;i < n - 1;++i)
		t1.push_back(v[i]);
	for(int i = 1;i < n;++i)
		t2.push_back(v[i]);
	int ans = max(ans, solve(t1));
	ans = max(ans, solve(t2));
	
	if(n > 4)
	{
		vector<int> tmp;
		for(int i = 2;i <= n - 3;++i)
			tmp.push_back(v[i]);
		int ret = solve(tmp);
		ans = max(ans, v[0] + v[n - 1] + ret);
	}
	cout << ans << "\n";
}