Cod sursa(job #3365903)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 27 septembrie 2026 17:01:51
Problema Oo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 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 start, int m)
{
    dp[1]=a[start];
    dp[2]=max(a[start], a[start+1]);
    dp[3]=max(dp[2], a[start+2]);
    for(int i=4; i<=m; i++)
    {
        dp[i]=max(dp[i-1], dp[i-3]+a[start+i-1]);
    }
    return dp[m];
}
int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
    {
        fin >> v[i];
    }
    if(n<2)
    {
        fout << 0 << "\n";
        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] << "\n";
        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 << "\n";
        return 0;
    }
    a[n+1]=a[1];
    a[n+2]=a[2];
    fout << max(max(rezolva(2, n-1), rezolva(3, n-1)), rezolva(4, n-1)) << "\n";
    return 0;
}