Cod sursa(job #1134117)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 5 martie 2014 23:42:49
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 100002;
const int inf = 1e8;

int a[Nmax];
int dp[Nmax];
int N, sol;

int main()
{
    ifstream f("oo.in");
    ofstream g("oo.out");

    f >> N;

    for ( int i = 1; i <= N; ++i )
            f >> a[i];

    dp[0] = dp[1] = -inf;
    dp[2] = a[1] + a[2];

    for ( int i = 3; i <= N - 1; ++i )
            dp[i] = max( dp[i - 1], dp[i - 3] + a[i] + a[i - 1] );

    sol = max( sol, dp[N - 1] );

    dp[0] = -inf;
    dp[1] = dp[2] = a[1] + a[N];

    for ( int i = 3; i <= N - 2; ++i )
            dp[i] = max( dp[i - 1], dp[i - 3] + a[i] + a[i - 1] );

    sol = max( sol, dp[N - 2] );

    dp[0] = dp[1] = dp[2] = 0;

    for ( int i = 3; i <= N; ++i )
            dp[i] = max( dp[i - 1], dp[i - 3] + a[i] + a[i - 1] );

    sol = max( sol, dp[N] );

    g << sol << "\n";

    return 0;
}