Cod sursa(job #332712)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 19 iulie 2009 13:46:12
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
# include <algorithm>
using namespace std;

# define DIM 100001

int n, a[ DIM ], sol[ DIM ];

inline int max ( int x, int y ) {

    if ( x > y )
        return x;

    return y;
}

int calc_sol0 () {

    int i;

    sol[ 1 ] = a[ n ] + a[ 1 ];
    sol[ 2 ] = max ( a[ 1 ] + a[ 2 ], sol[ 1 ] );
    for ( i = 3; i <= n - 2; ++ i )
        sol[ i ] = max ( sol[ i - 3 ] + a[ i - 1 ] + a[ i ], sol[ i - 1 ] );

    return sol[ n - 2 ];
}

int calc_sol1 () {

    int i;

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

    return sol[ n - 1 ];
}

int calc_sol2 () {

    int i;

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

    return sol[ n ];
}

void solve () {

    int i;

    scanf ( "%d", &n );
    for ( i = 1; i <= n; ++ i )
        scanf ( "%d", &a[ i ] );
    printf ( "%d", max ( max ( calc_sol0 (), calc_sol1 () ), calc_sol2 () ) );
}

int main () {

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

    solve ();

    return 0;
}