Cod sursa(job #131506)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 3 februarie 2008 21:06:14
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <math.h>

long n, i, sum, a[100010], c[100010], maxim;

long max(long num1, long num2) {
	if (num1 < num2) {
		return num2;
	}
	return num1;
}

int main() {
	freopen("oo.in", "r", stdin);
	freopen("oo.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &a[i]);
	}
	//dinamica I
	c[0] = 0;
	c[1] = 0;
	c[2] = a[1] + a[2];
	for (i = 3; i < n; ++i) {
		c[i] = max(c[i - 3] + a[i - 1] + a[i], c[i - 1]);
	}
	maxim = c[n - 1];
	for (i = 1; i <= n; ++i) {
		c[i] = 0;
	}
	//dinamica II
	c[3] = a[2] + a[3];	
	for (i = 3; i <= n; ++i) {
		c[i] = max(c[i - 3] + a[i - 1] + a[i], c[i - 1]);
	}
	maxim = max(maxim, c[n]);
	
	
	//dinamica III
	for (i = 1; i <= n; ++i) {
		c[i] = 0;
	}
	
	n -= 2;
	for (i = 4; i <= n; ++i) {
		c[i] = max(c[i - 1], c[i - 3] + a[i - 1] + a[i]);
	}
	maxim = max(maxim, c[n] + a[1] + a[n + 2]);
	
	
	printf("%ld\n", maxim);

	return 0;
}