Cod sursa(job #235206)

Utilizator mist000000 mist Data 23 decembrie 2008 01:04:11
Problema Oo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>

using namespace std;

long n;
int *sectors;
// max obtainable if we skip sector k (respectively use sector k and k-1)
long *skip, *use;

void compute()
{
	for (long i = 2; i < n; i++) {
		use[i] = sectors[i] + sectors[i - 1] + skip[i - 2];
		skip[i] = max(use[i - 1], skip[i - 1]);
	}
}

int main()
{
	ifstream in("oo.in");
	in >> n;
	sectors = new int[n + 1];
	for (long i = 0; i < n; i++) {
		in >> sectors[i];
	}
	in.close();

	ofstream out("oo.out");
	if (n == 2) {
		out << sectors[0] + sectors[1] << '\n';
	} else {
		use = new long[n + 1];
		skip = new long[n + 1];

		// first case: use sectors 0 and 1, and skip sector n-1
		use[0] = skip[0] = 0;
		use[1] = sectors[0] + sectors[1];
		skip[1] = 0;
		compute();
		long v1 = skip[n - 1];

		// second case: 'rotate' vector to the left
		// (actually append sector 0 to the end)
		// skip sectors 1 and 2, use or skip sector 0 at end

		// append sector 0 at the end
		sectors[n] = sectors[0];
		// rotate sectors
		sectors++;
		// force skipping of sectors 1 and 2 (after rotation)
		use[0] = skip[0] = 0;
		use[1] = skip[1] = 0;
		compute();
		long v2 = max(use[n - 1], skip[n - 1]);
		sectors--;

		delete[] use;
		delete[] skip;

		out << max(v1, v2) << '\n';
	}
	delete[] sectors;
	out.close();
	return 0;
}