Pagini recente » Cod sursa (job #2963299) | Cod sursa (job #2191795) | Cod sursa (job #495104) | Cod sursa (job #1810243) | Cod sursa (job #900801)
Cod sursa(job #900801)
#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);
}