Cod sursa(job #32794)

Utilizator azotlichidAdrian Vladu azotlichid Data 18 martie 2007 14:59:21
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define NMAX 100005
#define INF  999999999
int N, i, j, Ans = 0, a[NMAX], m[2][NMAX];

void shit(void)
{
    for (i = 2; i < N; i ++)
    {
        m[0][i] = max(m[0][i-1], m[1][i-1]);
        if ((m[1][i] = a[i-1]+a[i]+m[0][i-2]) < 0)
            m[1][i] = -INF;
    }
}

void crap(void)
{
    m[0][0] = 0, m[1][0] = -INF;
    m[0][1] = 0, m[1][1] = -INF;
    shit();
    Ans = max(Ans, max(m[0][N-1], m[1][N-1]));

    m[0][0] =    0, m[1][0] = -INF;
    m[0][1] = -INF, m[1][1] = a[0]+a[1];
    shit();
    Ans = max(Ans, m[0][N-1]);
}

int main(void)
{
    freopen("oo.in", "r", stdin);
    freopen("oo.out", "w", stdout);
    scanf("%d", &N);
    for (i = 0; i < N; i ++)
        scanf("%d", &a[i]);

    crap();
    for (i = N; i >= 1; i --) a[i] = a[i-1];
    a[0] = a[N];
    crap();

    printf("%d\n", Ans);
    return 0;
}