Cod sursa(job #3340296)

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

using namespace std;

int n;
int v[200005];
long long dp[200005];

long long solve_linear(int st, int dr)
{
    int len = dr - st + 1;
    if (len < 2) return 0;

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

    // dp[i] = profitul maxim folosind primele i elemente din intervalul selectat
    for (int i = 2; i <= len; i++)
    {
        // Opțiunea 1: Nu formăm o pereche care se termină la al i-lea element
        dp[i] = dp[i-1];

        // Opțiunea 2: Formăm perechea (i-1, i)
        // Valoarea perechii: v[st + i-2] + v[st + i-1]
        // Trebuie să sărim peste 2 elemente (cele care s-au speriat)
        // Deci adunăm dp[i-4]
        long long current_pair = (long long)v[st + i - 2] + v[st + i - 1];
        long long prev = (i >= 4) ? dp[i - 4] : 0;

        if (current_pair + prev > dp[i])
        {
            dp[i] = current_pair + prev;
        }
    }
    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];
        v[i + n] = v[i]; // Dublăm pentru a gestiona circularitatea
    }

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

    long long max_total = 0;

    // Testăm toate punctele de rupere posibile pentru a fi siguri 100%
    // Orice configurație optimă pe cerc va fi "liniară" în cel puțin una din aceste ferestre
    max_total = max(max_total, solve_linear(0, n - 1));
    max_total = max(max_total, solve_linear(1, n));
    max_total = max(max_total, solve_linear(2, n + 1));
    max_total = max(max_total, solve_linear(3, n + 2));

    fout << max_total << endl;

    return 0;
}