Cod sursa(job #3356279)

Utilizator rares89_Dumitriu Rares rares89_ Data 30 mai 2026 16:23:04
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#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;
}