Cod sursa(job #3341526)

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

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

int n;
int v[100005];
int p[100005]; // pair sums

// Run the suma2 DP on p[l..r], return max sum
int solve(int l, int r) {
    int len = r - l + 1;
    if (len <= 0) return 0;

    vector<int> dp(len + 2, 0);
    // reindex: dp[1] = p[l], dp[2] = p[l+1], ...
    dp[0] = 0;
    dp[1] = max(0, p[l]);
    for (int i = 2; i <= len; i++) {
        dp[i] = max(dp[i - 1], dp[i - 2] + p[l + i - 1]);
    }
    return dp[len];
}

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

    // Build pair sums (circular)
    for (int i = 1; i <= n; i++)
        p[i] = v[i] + v[i % n + 1]; // p[n] = v[n]+v[1]

    // Case 1: pairs p[1..n-1] (can't use p[n] since it overlaps with p[1])
    int ans1 = solve(1, n - 1);
    // Case 2: pairs p[2..n]
    int ans2 = solve(2, n);

    fout << max(ans1, ans2);
    return 0;
}