Pagini recente » Borderou de evaluare (job #130612) | Borderou de evaluare (job #432667) | Cod sursa (job #235206)
Cod sursa(job #235206)
#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;
}