Cod sursa(job #1210571)

Utilizator mihaimusatMihai Musat mihaimusat Data 20 iulie 2014 14:54:50
Problema Oo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<cstdio>
#include<algorithm>

using namespace std;

#define NMAX 100002

int n,v[NMAX];
int dp[NMAX];

int rez(int st,int sf)
{
    int i;

    for(i=0;i<st;++i)
        dp[i]=0;
    for(i=0;i<=3 && st+i<=sf;++i)
        dp[st+i]=v[st+i]+v[st-1+i];

    for(i=st+4;i<=sf;++i)
        dp[i]=max(dp[i-3],max(dp[i-4],dp[i-5]))+v[i]+v[i-1];

    return max(dp[sf],max(dp[sf-1],dp[sf-2]));
}

int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    int i,r1,r2,r3,sol;

    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);

    r1=rez(2,n-1);
    r2=rez(3,n);
    r3=rez(4,n-2)+v[1]+v[n];

    sol=max(r1,max(r2,r3));

    printf("%d\n",sol);

    return 0;
}