Cod sursa(job #3340284)

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

// DP liniar pe intervalul [start, end] (inclusiv)
long long dp_linear(const vector<int>& a, int start, int end) {
    int N = a.size();
    int len = end - start + 1;

    if (len <= 0) return 0;
    if (len == 1) return 1LL * a[start] + a[(start + 1) % N];
    if (len == 2)
        return max(1LL * a[start] + a[(start + 1) % N],
                   1LL * a[start + 1] + a[(start + 2) % N]);

    // Inițializare
    long long dp0 = 0; // dp[i-3]
    long long dp1 = 1LL * a[start] + a[(start + 1) % N]; // dp[i-2]
    long long dp2 = max(dp1, 1LL * a[start + 1] + a[(start + 2) % N]); // dp[i-1]

    long long dp_curr;

    for (int i = start + 2; 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(const vector<int>& a) {
    int N = a.size();
    if (N == 2) return 1LL * a[0] + a[1];

    // Caz 1: ignorăm ultima pereche (N-1,0)
    long long case1 = dp_linear(a, 0, N - 2);

    // Caz 2: ignorăm prima pereche (0,1)
    long long case2 = dp_linear(a, 1, N - 1);

    return max(case1, case2);
}

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

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

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