Cod sursa(job #3038860)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 27 martie 2023 20:59:52
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");

const int nmax = 1e5;
int n;
int v[nmax + 1]{0};
int dp[nmax + 1]{0};

int solve(int l, int r) {
	if (r - l < 1) {
		return 0;
	}
	// 0 1 2 3
	memset(dp, 0, sizeof(int) * (nmax + 1));
	dp[2] = v[l] + v[l + 1];
	for (int i = 3; i <= r - l + 1; ++i) {
		dp[i] = v[l + i - 2] + v[l + i - 1] + dp[i - 3];
		dp[i] = max(dp[i], dp[i - 1]);
	}
	return dp[r - l + 1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fin >> n;
	for (int i = 1; i <= n; ++i) {
		fin >> v[i];
	}
	fout << max({ v[1] + v[2] + solve(4, n - 1), // luam primele 2
				  v[1] + v[n] + solve(3, n - 2), // luam prima si ultima
				  solve(2, n) }); // nu luam prima
}