Cod sursa(job #1134116)

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

using namespace std;

const int Nmax = 100002;

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[1] = 0;
    dp[2] = dp[3] = dp[4] = a[1] + a[2];

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

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

    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] );

    dp[1] = dp[2] = dp[3] = a[1] + a[N];

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

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

    g << sol << "\n";

    return 0;
}