Cod sursa(job #31427)

Utilizator astronomyAirinei Adrian astronomy Data 15 martie 2007 23:30:02
Problema Oo Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>

#define MAXN (1 << 14)
#define max(a,b) ((a) > (b) ? (a) : (b))

int N, A[MAXN], best[MAXN], res;

void solve(void)
{
    int i;

    // iau 1 si 2
    best[2] = best[3] = best[4] = A[1]+A[2];
    for(i = 5; i < N; i++)
        best[i] = max(best[i-1], A[i]+A[i-1]+best[i-3]);
    res = best[N-1];

    // nu iau 1 si 2
    best[0] = best[1] = best[2] = 0;
    for(i = 3; i <= N; i++)
        best[i] = max(best[i-1], A[i]+A[i-1]+best[i-3]);
    res = max(res, best[N]);

    // iau 1 si N
    best[1] = best[2] = best[3] = A[1]+A[N];
    for(i = 4; i < N-1; i++)
        best[i] = max(best[i-1], A[i]+A[i-1]+best[i-3]);
    res = max(res, best[N-2]);
}

void read_data(void)
{
    int i;

    scanf("%d\n", &N);

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

void write_data(void)
{
    printf("%d\n", res);
}

int main(void)
{
    freopen("oo.in", "rt", stdin);
    freopen("oo.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}