Cod sursa(job #2948880)

Utilizator CalinHanguCalinHangu CalinHangu Data 28 noiembrie 2022 18:05:55
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

ifstream in("oo.in");
ofstream out("oo.out");

const int NMAX = 1e5;

int n, v[NMAX + 5], dp[NMAX + 5], ans;

void clear_dp(){
    for(int i = 1; i <= n + 1; ++i)
        dp[i] = 0;
}

int seq_calc(int l, int r){
    dp[l + 1] = v[l] + v[l + 1];
    for(int i = l + 2; i <= r; ++i){
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);

    }
    int x = dp[r];
    clear_dp();
    return x;
}

void solve(){
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
    v[n + 1] = v[1];
    ans = seq_calc(1, n - 1);
    ans = max(ans, seq_calc(2, n));
    ans = max(ans, seq_calc(3, n + 1));
    out << ans << '\n';
}

int main()
{
    solve();
    return 0;
}