Cod sursa(job #3281931)

Utilizator ALEXANDRUspargoaseAlexandru Joita ALEXANDRUspargoase Data 4 martie 2025 09:06:18
Problema Oo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int solve_linear(const vector<int> &a, int start, int end)
{
    int n = end - start + 1; // numărul de elemente din subsecvență
    // dp[i] va reprezenta maximul de ouă colectate din subsecvența care începe la poziția i (reindexată de la start)
    // Alocăm câteva poziții extra pentru a evita verificări de frontieră
    vector<int> dp(n + 4, 0);

    // Cazurile de bază:
    // Dacă avem doar 1 element, nu putem forma o pereche.
    dp[n] = 0;
    if (n >= 2)
        dp[n - 1] = a[start + n - 2] + a[start + n - 1];

    // Calculăm dp de la i = n-2 până la 1
    for (int i = n - 2; i >= 1; i--)
    {
        int pairVal = a[start + i - 1] + a[start + i]; // alegem perechea (i, i+1)
        dp[i] = max(dp[i + 1], pairVal + dp[i + 3]);
    }
    return dp[1];
}

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

    int N;
    fin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++)
    {
        fin >> a[i];
    }

    if (N == 2)
    {
        fout << a[0] + a[1] << "\n";
        return 0;
    }

    // Deoarece vectorul a este 0-indexat, iar în solve_linear considerăm startul ca 1-indexat:
    // Pentru subproblema A: folosim sectoarele 1..(N-1) -> echivalează cu indexii 0..(N-2)
    int solA = solve_linear(a, 0, N - 2);
    // Pentru subproblema B: folosim sectoarele 2..N -> echivalează cu indexii 1..(N-1)
    int solB = solve_linear(a, 1, N - 1);

    int solC = solve_linear(a, 2, N);
    fout << max(solC, max(solA, solB)) << "\n";
    return 0;
}