Cod sursa(job #3180102)

Utilizator vladutzu_finutzuVlad Cacenschi vladutzu_finutzu Data 4 decembrie 2023 17:10:35
Problema Oo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("oo.in");
ofstream cout("oo.out");

int compute(const vector<int>& v){
    const int n = v.size() - 1;
    vector<int> dp(n + 1);

    dp[2] = v[1] + v[2];
    for(int i=3; i<n; i++)
        dp[i] = max(dp[i-1], dp[i-3] + v[i] + v[i-1]);
    
    int sol = dp[n - 1];

    dp.clear();
    dp.resize(n + 1);

    for(int i=3; i<=n; i++)
        dp[i] = max(dp[i-1], dp[i-3] + v[i] + v[i-1]);

    return max(sol, dp[n]);
}

int main(){
    int n;
    cin>>n;

    vector<int> v(n+1);

    for(int i=1; i<=n; i++)
        cin>>v[i];
    
    int sol = compute(v);

    v.push_back(v[1]);
    v.erase(v.begin());
    v.erase(v.begin() + 1);

    sol = max(sol, compute(v));

    cout<<sol;

    return 0;
}