Cod sursa(job #1011868)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 17 octombrie 2013 17:57:57
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int Nmax = 100005;

int v[ Nmax ],DP[4][ Nmax ],N;

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

inline void init()
{
    DP[0][2] = v[1]+v[2];
    DP[1][3] = v[2]+v[3];
    DP[2][4] = v[3]+v[4];
}

inline void solve()
{
    int i;
    for(i = 3; i < N; ++i )
        DP[0][i] = max( DP[0][i-1] , DP[0][i-3]+v[i-1]+v[i]);
    DP[0][N] = DP[0][N-1];
    for(i = 4; i <= N; ++i)
        DP[1][i] = max( DP[1][i-1] , DP[1][i-3]+v[i-1]+v[i]);
    for(i = 5; i - 1 <= N; ++i)
        DP[2][i] = max( DP[2][i-1] , DP[2][i-3]+v[i-1]+v[i]);
    printf("%d", max(DP[0][N],max(DP[1][N],DP[2][N+1])));
}

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

    read();
    init();
    solve();

    return 0;
}