Cod sursa(job #3340292)

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

using namespace std;

// Funcție care calculează maximul pe un șir liniar
// dp[i] = maximul folosind elementele de la 0 la i
long long solve_linear(const vector<int>& a) {
    int n = a.size();
    if (n < 2) return 0;

    vector<long long> dp(n, 0);
    for (int i = 1; i < n; i++) {
        // Opțiunea 1: Nu luăm o pereche care se termină la i
        dp[i] = dp[i - 1];

        // Opțiunea 2: Luăm perechea (i-1, i)
        long long current_pair = a[i] + a[i - 1];
        if (i >= 3) {
            dp[i] = max(dp[i], current_pair + dp[i - 3]);
        } else {
            dp[i] = max(dp[i], current_pair);
        }
    }
    return dp[n - 1];
}

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 << v[0] + v[1] << endl;
        return 0;
    }

    long long max_oua = 0;

    // Cazul 1: NU folosim legătura dintre ultimul și primul (v[n-1] + v[0])
    // Rezolvăm liniar normal: 0, 1, 2, ..., n-1
    max_oua = max(max_oua, solve_linear(v));

    // Cazul 2: Forțăm perechea (v[n-1], v[0])
    // Asta blochează v[n-2] și v[1].
    // Rămâne de calculat optimul pentru segmentul [2, n-3]
    vector<int> c2;
    for (int i = 2; i <= n - 3; i++) c2.push_back(v[i]);
    max_oua = max(max_oua, (long long)v[n - 1] + v[0] + solve_linear(c2));

    // Cazul 3: Forțăm perechea (v[0], v[1])
    // Asta blochează v[n-1] și v[2].
    // Rămâne de calculat optimul pentru segmentul [3, n-2]
    vector<int> c3;
    for (int i = 3; i <= n - 2; i++) c3.push_back(v[i]);
    max_oua = max(max_oua, (long long)v[0] + v[1] + solve_linear(c3));

    fout << max_oua << endl;

    return 0;
}