Cod sursa(job #2296530)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 decembrie 2018 19:19:42
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("oo.in");
ofstream fout("oo.out");

int N, v[100005];
int dp[100005];

void Read()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> v[i];
}

void Solve()
{
    int sol;

    ///iau primul si al doilea ou
    sol = dp[4] = dp[3] = dp[2] = v[1] + v[2];

    for(int i = 5; i <= N - 1; i++)
    {
        dp[i] = max(dp[i - 1], v[i - 1] + v[i] + dp[i - 3]);
        sol = max(dp[i], sol);
    }

    ///iau al doilea si al treilea ou
    memset(dp, 0, sizeof(dp));
    dp[5] = dp[4] = dp[3] = v[2] + v[3];
    sol = max(dp[3], sol);

    for(int i = 6; i <= N; i++)
    {
        dp[i] = max(dp[i - 1], v[i - 1] + v[i] + dp[i - 3]);
        sol = max(dp[i], sol);
    }

    ///iau ultimul si primul ou
    memset(dp, 0, sizeof(dp));
    dp[3] = dp[2] = dp[1] = v[N] + v[1];
    sol = max(dp[1], sol);

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

    fout << sol;
}

int main()
{
    Read();

    Solve();

    return 0;
}