Cod sursa(job #1937166)

Utilizator Bodo171Bogdan Pop Bodo171 Data 23 martie 2017 19:20:41
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;
long long best[100005],a[100005];
int n,i,j;
long long dp(int l,int r)
{
    for(i=1;i<=n;i++)
        best[i]=0;
    for(i=l;i<=r;i++)
    {
        best[i]=1LL*best[i-1];
        if(i>=l+1)
            {
             if(i>=3&&1LL*(best[i-3]+a[i-1]+a[i])>best[i])
                best[i]=1LL*(best[i-3]+a[i-1]+a[i]);
              if(a[i-1]+a[i]>best[i])
                best[i]=1LL*(a[i-1]+a[i]);
            }
    }
    return best[r];
}
int main()
{
    ifstream f("oo.in");
    ofstream g("oo.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>a[i];
    g<<max(max(dp(1,n-1),dp(3,n-2)+a[1]+a[n]),dp(2,n));
    return 0;
}