Cod sursa(job #38278)

Utilizator silviugSilviu-Ionut Ganceanu silviug Data 25 martie 2007 16:56:32
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>

#define MAXN (1 << 17)
#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);

    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;
}