Cod sursa(job #900801)

Utilizator mika17Mihai Alex Ionescu mika17 Data 28 februarie 2013 21:55:23
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <vector>

int main() {

	int N;
	std::ifstream in("oo.in"); std::ofstream out("oo.out");

	in >> N;
	std::vector<int> A(N), B;
	for(int i=0;i<N;++i) in>>A[i];

	if(N == 2) {
		out<<A[0] + A[1];
		return 0;
	}
	if(N == 3) {
		out<<std::max(A[0]+A[1],std::max(A[1]+A[2],A[2]+A[0]));
		return 0;
	}

	B.assign(N,0);
	B[1] = A[0] + A[1]; B[2] = B[3] = B[1];
	for(int i=4;i<N-1;++i) {
		B[i] = std::max(A[i] + A[i - 1] + B[i - 3],B[i - 1]);
	}
	int s1 = B[N - 2];

	B.assign(N,0);
	B[0] = A[N - 1] + A[0];
	B[1] = B[2] = B[0];

	for(int i=3;i<N-2;++i) {
		B[i] = std::max(A[i] + A[i - 1] + B[i - 3],B[i - 1]);
	}

	int s2 = B[N - 3];

	B.assign(N + 1,0);
	//shift the array here
	B[0] = A[N - 2] + A[N - 1]; B[1] = B[2] = B[0];
	for(int i=2;i<N-2;++i)
		B[i + 1] = std::max(A[i] + A[i - 1] + B[i - 2],B[i]);

	int s3 = B[N - 3];

	out << std::max(std::max(s1,s2),s3);
}