Cod sursa(job #1739784)

Utilizator silkMarin Dragos silk Data 10 august 2016 11:18:51
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <cstring>
#define NMax 100005
#define MAX(a,b)((a)>(b)?(a):(b))

int best[NMax];
int v[NMax];

int main(){
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);

    int i,N,ans;

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

    best[3] = v[1] + v[2];
    for( i = 4; i <= N; ++i )
    best[i] = MAX( best[i-2], MAX( best[i-1],MAX( best[i-3] + v[i-2] + v[i-1], best[i-4] + v[i-3] + v[i-2] ) ) );

    ans = best[N];
    memset(best,0,sizeof(best));

    best[4] = v[2] + v[3];
    for( i = 5; i <= N+1; ++i )
    best[i] = MAX( best[i-2], MAX( best[i-1],MAX( best[i-3] + v[i-2] + v[i-1], best[i-4] + v[i-3] + v[i-2] ) ) );

    ans = MAX( ans, best[N+1] );
    memset(best,0,sizeof(best));

    best[2] = v[1] + v[N];
    best[3] = best[4] = best[2];
    best[5] = best[2] + v[3] + v[4];
    for( i = 6; i < N; ++i )
    best[i] = MAX( best[i-2], MAX( best[i-1], MAX( best[i-3] + v[i-2] + v[i-1], best[i-4] + v[i-3] + v[i-2] ) ) );

    ans = MAX( ans, best[N-1] );


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



return 0;
}