Cod sursa(job #1501301)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 13 octombrie 2015 10:59:21
Problema Oo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 100001;
int N;
int v[NMAX], d[NMAX];

int add (int a, int x) {
	if (x == -1) {
		if (a - 1 == 0) {
			return N;
		}
		return a - 1;
	}

	if (x == 1) {
		if (a + 1 == N + 1) {
			return 1;
		}
		return a + 1;
	}

	if (x == -2) {
		a -= 2;
		a %= N;
		if (a == 0) {
			return N;
		}
		if (a == N + 1) {
			return 1;
		}
		return a;
	}
}

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

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

	if (N == 2) {
		printf ("%d\n", v[1] + v[2]);
		return 0;
	}
	if (N == 3) {
		printf ("%d\n", max (max (v[1] + v[2], v[2] + v[3]), v[1] + v[3]));
		return 0;
	}
	if (N == 4) {
		printf ("%d\n", max (max (v[1] + v[2], v[2] + v[3]), max (v[3] + v[4], v[4] + v[1])));
		return 0;
	}

	if (v[1] + v[2] >= v[N] + v[1]) {
		d[3] = v[1] + v[2];
		N--;
	}
	else {
		d[2] = d[3] = v[N] + v[1];
		N -= 2;
	}

	d[4] = d[3];
	if (d[4] < v[1] + v[3]) {
		d[4] = v[1] + v[3];
	}
    else {
		if (d[4] < v[2] + v[3]) {
			d[4] = v[2] + v[3];
		}
    }

	int cnt = 1;
	for (int i = 3; i <= N, cnt < N; i = add (i, 1), cnt ++) {
		d[add (i, 1)] = max (d[i], v[i] + v[add (i, -1)] + d[add (i, - 2)]);
	}
	d[1] = max (d[1], d[N + 1]);
	d[2] = max (d[2], v[1] + v[N] + d[N - 1]);

	printf ("%d\n", d[1]);

	return 0;
}