Cod sursa(job #3340297)

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

using namespace std;

int n, v[100005], dp[100005];

// Calculeaza maximul pe un sir liniar
int solve_linear(int start, int end)
{
    if (start > end) return 0;
    int len = end - start + 1;
    if (len < 2) return 0;

    // Resetare dp pentru segmentul curent
    for (int i = 0; i <= len; i++) dp[i] = 0;

    // dp[i] = profitul maxim folosind primele i elemente din segment
    for (int i = 2; i <= len; i++)
    {
        dp[i] = dp[i - 1]; // Nu luam pereche la i

        int val_pereche = v[start + i - 2] + v[start + i - 1];
        int anterior = (i >= 4) ? dp[i - 4] : 0;

        if (val_pereche + anterior > dp[i])
        {
            dp[i] = val_pereche + anterior;
        }
    }
    return dp[len];
}

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

    if (!(fin >> n)) return 0;
    for (int i = 0; i < n; i++) fin >> v[i];

    if (n == 2)
    {
        fout << v[0] + v[1] << endl;
        return 0;
    }

    int sol = 0;

    // Cazul 1: NU folosim perechea (v[n-1], v[0])
    // Rezolvam pur si simplu liniar
    sol = max(sol, solve_linear(0, n - 1));

    // Cazul 2: FORȚĂM perechea (v[n-1], v[0])
    // Aceasta blocheaza v[n-2] si v[1].
    // Ramane de calculat optimul pe segmentul [2, n-3]
    if (n >= 4)
    {
        sol = max(sol, v[n - 1] + v[0] + solve_linear(2, n - 3));
    }

    // Cazul 3: FORȚĂM perechea (v[0], v[1])
    // Aceasta blocheaza v[n-1] si v[2].
    // Ramane de calculat optimul pe segmentul [3, n-2]
    if (n >= 4)
    {
        sol = max(sol, v[0] + v[1] + solve_linear(3, n - 2));
    }

    // Cazul 4: FORȚĂM perechea (v[1], v[2])
    // Aceasta blocheaza v[0] si v[3].
    // Ramane de calculat optimul pe segmentul [4, n-1]
    if (n >= 5)
    {
        sol = max(sol, v[1] + v[2] + solve_linear(4, n - 1));
    }

    fout << sol << endl;
    return 0;
}