Cod sursa(job #3340291)

Utilizator hansHans Silviu hans Data 13 februarie 2026 16:15:42
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int solve_linear(int start, int end, const vector<int>& v) {
    if (start > end) return 0;
    int n = end - start + 1;
    vector<int> dp(n + 1, 0);

    // Ajustăm indexarea pentru a lucra local de la 1 la n
    auto val = [&](int i) { return v[start + i - 2]; };

    for (int i = 2; i <= n; ++i) {
        int gain = val(i-1) + val(i);
        int prev = (i >= 4) ? dp[i-4] : 0;
        dp[i] = max(dp[i-1], gain + prev);
    }
    return dp[n];
}

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

    int N;
    if (!(fin >> N)) return 0;

    vector<int> v(N);
    for (int i = 0; i < N; ++i) {
        fin >> v[i];
    }

    if (N < 2) {
        fout << 0;
        return 0;
    }

    // Rulăm DP pe 4 variante de "tăiere" a cercului pentru a acoperi
    // toate posibilitățile de excludere la capete.
    int ans = 0;

    // 1. Forțăm să NU se lege N cu 1 (liniar simplu)
    ans = max(ans, solve_linear(0, N - 1, v));

    // 2. Forțăm perechea (0, 1) -> blochează N-1 și 2
    ans = max(ans, v[0] + v[1] + solve_linear(3, N - 2, v));

    // 3. Forțăm perechea (N-1, 0) -> blochează N-2 și 1
    ans = max(ans, v[N-1] + v[0] + solve_linear(2, N - 3, v));

    // 4. Forțăm perechea (1, 2) -> blochează 0 și 3
    ans = max(ans, v[1] + v[2] + solve_linear(4, N - 1, v));

    fout << ans << endl;

    return 0;
}