Cod sursa(job #3340290)

Utilizator hansHans Silviu hans Data 13 februarie 2026 16:13:36
Problema Oo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
int a[MAXN];

// DP pe interval de perechi [start..end]
long long dp_linear(int start, int end, int N) {
    long long dp0 = 0; // maxim pana la i-3
    long long dp1 = 0; // maxim pana la i-2
    long long dp2 = 0; // maxim pana la i-1
    long long dp_curr;

    for (int i = start; i <= end; i++) {
        long long pair_sum = 1LL * a[i % N] + a[(i + 1) % N];
        dp_curr = max(dp2, dp0 + pair_sum);
        dp0 = dp1;
        dp1 = dp2;
        dp2 = dp_curr;
    }
    return dp2;
}

long long max_oua(int N) {
    if (N == 2) return 1LL * a[0] + a[1];

    // Caz 1: ignoram ultima pereche (N-1,0)
    long long case1 = dp_linear(0, N - 2, N);

    // Caz 2: ignoram prima pereche (0,1)
    long long case2 = dp_linear(1, N - 1, N);

    return max(case1, case2);
}

int main() {
    freopen("oo.in", "r", stdin);
    freopen("oo.out", "w", stdout);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];

    cout << max_oua(N) << "\n";
    return 0;
}