Cod sursa(job #1933756)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 20 martie 2017 22:03:33
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int n;
const int Nmax=100000+5;
int a[Nmax],DP[Nmax],maxx;
int main()
{
    fin>>n;
    for(int i=1;i<=n;++i)
    {
        fin>>a[i];
        a[n+i]=a[i];
    }
    for(int r=1;r<=n;++r)
    {
        int lim=n+r;
        if(a[r]+a[r+1]>=a[r+1]+a[r+2])
        {
            lim--;
            DP[r]=a[r];
        }
        else DP[r]=0;
        for(int i=r+1;i<=lim-1;++i)
        {
            if(i>=3)DP[i]=max(DP[i-1],DP[i-3]+a[i-1]+a[i]);
            else DP[i]=DP[i-1];
            maxx=max(DP[i],maxx);
        }
        for(int i=r;i<=n+r;++i)DP[i]=0;
    }
    fout<<maxx;
    return 0;
}