Cod sursa(job #3341525)

Utilizator Maries_MihaiMaries Mihai Maries_Mihai Data 19 februarie 2026 20:28:45
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <Vector>
using namespace std;

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

#define nmax 100005
int n, v[nmax], p[nmax], dp[nmax];

// Run DP on p[l..r], return best sum with no two chosen pairs within distance 2
int solve(int l, int r) {
    if (l > r) return 0;

    int len = r - l + 1;
    // reindex locally: a[1..len] = p[l..r]
    // dp[i] = best sum using a[1..i]
    // dp[i] = max(dp[i-1], dp[i-3] + a[i])

    vector<int> a(len + 1), d(len + 4, 0);
    for (int i = 1; i <= len; i++)
        a[i] = p[l + i - 1];

    d[1] = max(0, a[1]);
    if (len >= 2) d[2] = max(d[1], a[2]);
    for (int i = 3; i <= len; i++)
        d[i] = max(d[i - 1], d[i - 3] + a[i]);

    return d[len];
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    for (int i = 1; i <= n; i++)
        p[i] = v[i] + v[i % n + 1];

    // Case 1: p[1..n-2]
    // Case 2: p[2..n-1]
    int ans = max(solve(1, n - 2), solve(2, n - 1));

    fout << ans;
    return 0;
}