Cod sursa(job #3359832)

Utilizator alex.iovita.23@gmail.comIovita Alexandru [email protected] Data 5 iulie 2026 01:00:39
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<bits/stdc++.h>

using namespace std;

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

int n , v[100001];

inline int sol(int start , int lend){
    if(start > lend) return 0;
    int lungime = lend - start + 1;
    if(lungime < 2) return 0;
    vector<int> dp(lungime + 1 , 0);
    dp[1] = 0; // Un singur sector nu poate forma o pereche
    dp[2] = v[start] + v[start + 1]; // Primele două sectoare formează prima pereche posibilă
    for(int i = 3 ; i <= lungime ; i++){
        int optiunea = dp[i - 1];
        // Opțiunea 2: Formăm o pereche din ultimele două sectoare (i - 1 și i)
        // Asta înseamnă că adunăm valoarea lor + ce aveam înainte ca vecinii lor să se sperie (dp[i - 4])
        int val1 = v[start + i - 2] + v[start + i - 1];
        int val2 = 0;
        if(i >= 4) val2 = dp[i - 4];
        int optiunea2 = val1 + val2;
        dp[i] = max(optiunea , optiunea2);
    }
    return dp[lungime];
}

int main(){
    fin >> n;
    for(int i = 1 ; i <= n ; i++) fin >> v[i];
    int scenariu1 = sol(2 , n);
    int scenariu2 = v[1] + v[2] + sol(4 , n - 1);
    int scenariu3 = v[1] + v[n] + sol(3 , n - 2);
    fout << max({scenariu1 , scenariu2 , scenariu3});
}