Cod sursa(job #3365904)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 27 septembrie 2026 17:26:38
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
long long n;
long long v[100005];
long long a[100005];
long long dp[100005];
long long rezolva(int l, int r)
{
    if(r-l==0) return a[l];
    if(r-l==1) return max(a[l], a[l+1]);
    if(r-l==2) return max(max(a[l], a[l+1]), a[l+2]);
    dp[1]=a[l];
    dp[2]=max(a[l], a[l+1]);
    dp[3]=max(dp[2], a[l+2]);
    for(int i=4; i<=r-l+1; i++)
    {
        dp[i]=max(dp[i-1], dp[i-3]+a[l+i-1]);
    }
    return dp[r-l+1];
}
int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
    {
        fin >> v[i];
    }
    if(n<2)
    {
        fout << 0;
        return 0;
    }
    for(int i=1; i<n; i++)
    {
        a[i]=v[i]+v[i+1];
    }
    a[n]=v[n]+v[1];
    if(n==2)
    {
        fout << a[1];
        return 0;
    }
    if(n<6)
    {
        long long max_p=0;
        for(int i=1; i<=n; i++)
        {
            max_p=max(max_p, a[i]);
        }
        fout << max_p;
        return 0;
    }
    fout << max(max(max(a[1]+rezolva(4, n-2), a[2]+rezolva(5, n-1)), a[3]+rezolva(6, n)), rezolva(4, n));
    return 0;
}