Cod sursa(job #2269059)

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

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

int solve(int i, bool canLast) {
	if (i >= n || (!canLast && i == n - 1)) {
		return 0;
	}

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

	if (i == 1) {
		return max(solve(i + 2, false) + a[i] + a[n], max(solve(i + 3, false) + a[i] + a[i + 1], solve(i + 1, true)));
	}
	else {
		cache[i][canLast] = max(solve(i + 3, canLast) + a[i] + a[i + 1], solve(i + 1, canLast));
		return cache[i][canLast];
	}

}

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;
}