Cod sursa(job #2269082)

Utilizator memecoinMeme Coin memecoin Data 25 octombrie 2018 18:22:28
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;

int a[100005];
int cache[100005][3];
int n;

int solve(int i, int status) {
	if (i >= n - status) {
		return 0;
	}

	if (cache[i][status] != 0) {
		return cache[i][status];
	}

	if (i == 1) {
		int v1 = solve(i + 2, 2) + a[i] + a[n];
		int v2 = solve(i + 3, 1) + a[i] + a[i + 1];
		int v3 = solve(i + 1, 0);
		return max(v1, max(v2,v3 ));
	}
	else {
		int v1 = solve(i + 3, status) + a[i] + a[i + 1];
		int v2 = solve(i + 1, status);
		cache[i][status] = max(v1, v2);
		return cache[i][status];
	}

}

int main() {
	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}

	printf("%d", solve(1, true));

	return 0;
}