Cod sursa(job #889667)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 24 februarie 2013 17:26:19
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int NMAX = 100005;
int n,i,a[NMAX],P[NMAX],DP[NMAX],A,B,C;
int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=a[1];
    for(i=1;i<=n;i++) P[i]=a[i]+a[i+1];

    DP[1]=DP[2]=DP[3]=P[1];
    for(i=4;i<=n-2;i++) DP[i]=max(DP[i-1],DP[i-3]+P[i]);
    A=DP[n-2];
    memset(DP,0,sizeof(DP));

    DP[2]=DP[3]=DP[4]=P[2];
    for(i=5;i<=n-1;i++) DP[i]=max(DP[i-1],DP[i-3]+P[i]);
    B=DP[n-1];
    memset(DP,0,sizeof(DP));

    DP[3]=DP[4]=DP[5]=P[3];
    for(i=6;i<=n;i++) DP[i]=max(DP[i-1],DP[i-3]+P[i]);
    C=DP[n];

    printf("%d\n",max(A,max(B,C)));
    return 0;
}