Cod sursa(job #1682939)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 10 aprilie 2016 13:27:38
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("oo.in");
ofstream g("oo.out");

const int Nmax = 100005;
int n, c[Nmax], DP[Nmax];

int main()
{
    f>>n;
    int sol = 0;
    for(int i = 1; i <= n; i++) f>>c[i];
    DP[1] = 0;
    DP[2] = c[1]+c[2];
    DP[3] = DP[2];
    for(int i = 4; i <= n - 1; i++)
    {
        DP[i] = max(DP[i-1], DP[i-3] + c[i-1]+c[i]);
        sol = max(sol, DP[i]);
    }
    DP[1] = 0;
    DP[2] = 0;
    DP[3] = c[3] + c[2];
    DP[4] = DP[3];
    for(int i = 5; i <= n; i++)
    {
        DP[i] = max(DP[i-1], DP[i-3] + c[i-1]+c[i]);
        sol = max(sol, DP[i]);
    }
    DP[1] = DP[2] = DP[3] = 0;
    DP[4] = c[3] + c[4];
    DP[5] = DP[4];
    c[n+1] = c[1];
    for(int i = 6; i <= n+1; i++)
    {
        DP[i] = max(DP[i-1], DP[i-3] + c[i-1]+c[i]);
        sol = max(sol, DP[i]);
    }
    g<<sol<<'\n';
    return 0;
}