Pagini recente » Cod sursa (job #3338284) | Diferente pentru problema/cezar intre reviziile 19 si 18 | Cod sursa (job #883878) | Cod sursa (job #3350066) | Cod sursa (job #3356279)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int n;
int a[100005];
long long p[100005];
long long solve(int L, int R) {
if (L > R) return 0;
int len = R - L + 1;
vector<long long> dp(len, 0);
for (int i = 0; i < len; ++i) {
long long take = p[L + i] + (i >= 3 ? dp[i - 3] : 0);
long long skip = (i >= 1 ? dp[i - 1] : 0);
dp[i] = max(take, skip);
}
return dp.back();
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> a[i];
}
for (int i = 1; i < n; ++i) {
p[i] = a[i] + a[i + 1];
}
p[n] = a[n] + a[1];
long long ans = 0;
if (n >= 1) ans = max(ans, p[1] + solve(4, n - 2));
if (n >= 2) ans = max(ans, p[2] + solve(5, n - 1));
if (n >= 3) ans = max(ans, p[3] + solve(6, n));
ans = max(ans, solve(4, n));
fout << ans << "\n";
fin.close();
fout.close();
return 0;
}