Cod sursa(job #235201)

Utilizator mist000000 mist Data 23 decembrie 2008 00:53:44
Problema Oo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 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];
	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];
		skip = new long[n];

		// 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: skip sectors 0 and 1, use or skip sector n-1
		use[0] = skip[0] = 0;
		// force skipping of sectors 0 and 1
		use[1] = skip[1] = 0;
		compute();
		long v2 = max(use[n - 1], skip[n - 1]);

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