Cod sursa(job #1340342)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 11 februarie 2015 19:27:35
Problema Oo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int MAXN = 100000;

int N, o[MAXN+1], answer, best[MAXN+1];

void citire()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; i++)
        scanf("%d",&o[ i ]);
}

void dinamica()
{
    best[ 2 ] = o[ 1 ] + o[ 2 ];
    best[ 4 ] = best[ 2 ];
    answer = best[ 2 ];
    for(int i = 5; i <= N - 1; i++)
        best[ i ] = max( o[ i ] + o[ i - 1 ] + best[ i - 3 ], best[ i - 1 ] );
    answer = max( answer, best[ N - 1 ] );

    best[ 1 ] = o[ 1 ] + o[ N ];
    best[ 3 ] = best[ 1 ];
    answer = max( answer, best[ 1 ] );
    for(int i = 4; i <= N - 2; i++)
        best[ i ] = max( o[ i ] + o[ i - 1 ] + best[ i - 3 ], best[ i - 1 ] );
    answer = max( answer, best[ N - 2 ] );

    best[ 3 ] = o[ 3 ] + o[ 2 ];
    best[ 4 ] = best[ 3 ];
    answer = max( answer, best[ 3 ] );
    for(int i = 6; i <= N; i++)
        best[ i ] = max( o[ i ] + o[ i - 1 ] + best[ i - 3 ], best[ i - 1 ] );
    answer = max( answer, best[ N ] );
}







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

    citire();

    dinamica();

    printf("%d",answer);

    return 0;
}