Cod sursa(job #3340295)

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

using namespace std;

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

// Calculeaza maximul pe un sir liniar de lungime 'len'
// folosind elementele din tabloul 'a'
int solve_linear(int a[], int len) {
    if (len < 2) return 0;

    // Initializam dp
    for (int i = 0; i <= len; i++) dp[i] = 0;

    // dp[i] = maximul folosind primele i elemente
    // O pereche (i-1, i) poate fi adunata daca precedenta
    // s-a terminat la i-4 (lasand i-2 si i-3 libere)
    for (int i = 2; i <= len; i++) {
        dp[i] = dp[i-1]; // Nu luam pereche la pozitia i

        int current_pair = a[i-1] + a[i-2];
        int prev_val = (i >= 4) ? dp[i-4] : 0;

        if (current_pair + prev_val > dp[i]) {
            dp[i] = current_pair + prev_val;
        }
    }
    return dp[len];
}

int temp[100005];

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;
    }

    // --- CAZUL 1: NU luam perechea (v[n-1], v[0]) ---
    // Rezolvam liniar pur si simplu de la 0 la n-1
    int rez1 = solve_linear(v, n);

    // --- CAZUL 2: LUAM perechea (v[n-1], v[0]) ---
    // Asta blocheaza v[1] si v[n-2].
    // Trebuie sa rezolvam restul elementelor: v[2], v[3], ..., v[n-3]
    int rez2 = 0;
    if (n >= 4) {
        int m = 0;
        for (int i = 2; i <= n - 3; i++) {
            temp[m++] = v[i];
        }
        rez2 = v[n-1] + v[0] + solve_linear(temp, m);
    } else {
        rez2 = v[n-1] + v[0];
    }

    fout << max(rez1, rez2) << endl;

    return 0;
}