Cod sursa(job #129462)

Utilizator DastasIonescu Vlad Dastas Data 29 ianuarie 2008 15:37:49
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>

const int maxn = 100002;

FILE *in = fopen("oo.in","r"), *out = fopen("oo.out","w");

int n;
int a[maxn];

int b[maxn];

inline int max(int x, int y)
{
    return x > y ? x : y;
}

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", &a[i]);
}

int answ;
void go()
{
    b[2] = a[1] + a[2];
    for ( int i = 3; i <= n; ++i )
        b[i] = max(b[i-1], a[i] + a[i-1] + b[i-3]);
    answ = max(answ, b[n-1]);

    b[2] = 0;
    for ( int i = 3; i <= n; ++i )
        b[i] = max(b[i-1], a[i] + a[i-1] + b[i-3]);
    answ = max(answ, b[n]);

    b[1] = b[2] = a[1] + a[n];
    for ( int i = 3; i < n - 1; ++i )
        b[i] = max(b[i-1], a[i] + a[i-1] + b[i-3]);
    answ = max(answ, b[n-2]);
}

int main()
{
    read();
    go();

    fprintf(out, "%d\n", answ);

    return 0;
}