Cod sursa(job #3340294)

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

using namespace std;

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

// Calculează profitul maxim pe un segment liniar [st, dr]
// Respectând regula: între două perechi alese [i-1, i] și [j-1, j]
// trebuie să existe cel puțin 2 elemente libere.
int solve_linear(int st, int dr) {
    if (st > dr || dr - st + 1 < 2) return 0;

    int len = dr - st + 1;
    // Resetăm doar porțiunea necesară din dp
    for (int i = 0; i <= len; i++) dp[i] = 0;

    // dp[i] = maximul folosind primele i elemente din segment (indexat de la 1)
    for (int i = 2; i <= len; i++) {
        // Opțiunea 1: Nu formăm o pereche care să se termine la elementul i
        dp[i] = dp[i - 1];

        // Opțiunea 2: Formăm perechea (i-1, i)
        // Valoarea perechii este v[indice_real_i-1] + v[indice_real_i]
        int current_pair = v[st + i - 2] + v[st + i - 1];

        if (i >= 4) {
            dp[i] = max(dp[i], current_pair + dp[i - 4]);
        } else {
            dp[i] = max(dp[i], current_pair);
        }
    }
    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 max_total = 0;

    // Strategia celor două "tăieri" fundamentale:

    // 1. Cazul în care NU alegem perechea formată din (v[n-1], v[0])
    // Rezolvăm liniar pe tot vectorul.
    max_total = max(max_total, solve_linear(0, n - 1));

    // 2. Cazul în care alegem perechea (v[n-1], v[0])
    // Această alegere obligă sectoarele v[n-2] și v[1] să fie libere.
    // Deci trebuie să găsim optimul pe restul elementelor rămase: [2, n-3]
    if (n >= 4) {
        max_total = max(max_total, v[n - 1] + v[0] + solve_linear(2, n - 3));
    }

    // 3. Cazul în care alegem perechea (v[0], v[1])
    // Această alegere obligă sectoarele v[n-1] și v[2] să fie libere.
    // Elementele rămase: [3, n-2]
    if (n >= 4) {
        max_total = max(max_total, v[0] + v[1] + solve_linear(3, n - 2));
    }

    // 4. Cazul în care alegem perechea (v[n-2], v[n-1])
    // Obligă v[n-3] și v[0] să fie libere.
    // Elementele rămase: [1, n-4]
    if (n >= 4) {
        max_total = max(max_total, v[n - 2] + v[n - 1] + solve_linear(1, n - 4));
    }

    fout << max_total << endl;
    return 0;
}