Cod sursa(job #3341527)

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

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

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

int solve(int l, int r) {
    if (l > r) return 0;
    int len = r - l + 1;

    vector<int> d(len + 1, 0);
    for (int i = 1; i <= len; i++) {
        int val = p[l + i - 1];
        int prev3 = (i >= 4) ? d[i - 3] : 0;
        d[i] = max(d[i - 1], prev3 + val);
    }

    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];

    // Three cases to handle circular conflicts
    int ans = solve(1, n - 2);           // exclude p[n-1] and p[n]
    ans = max(ans, solve(2, n - 1));     // exclude p[1] and p[n]
    ans = max(ans, solve(3, n));         // exclude p[1] and p[2]

    fout << ans;
    return 0;
}