Cod sursa(job #2612309)

Utilizator As932Stanciu Andreea As932 Data 8 mai 2020 20:08:00
Problema Oo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>

using namespace std;

ifstream cin("oo.in");
ofstream cout("oo.out");

const int nmax=100005;

int n;
int v[nmax],d[nmax];

//exista 3 variante prin care putem ajunge la maxim

int dp(int st,int en)
{
    d[st]=0;
    d[st+1]=v[st]+v[st+1];

    for(int i=st+2;i<=en;i++)
        d[i]=max(d[i-1],d[i-3]+v[i-1]+v[i]);

    return d[n];
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>v[i];

    v[n+1]=v[1];

    cout<<max(dp(1,n-1),max(dp(2,n),dp(3,n+1)));

    return 0;
}