Cod sursa(job #1928357)

Utilizator raulmuresanRaul Muresan raulmuresan Data 16 martie 2017 08:27:11
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
using namespace std;

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

const int NMAX = 100005;

int n, v[NMAX], d1[NMAX], d2[NMAX], d3[NMAX], i, sol;
int main()
{
    fin >> n;
    for(i=1;i<=n;i++)
    {
        fin >> v[i];
    }
    d1[1] = v[1] + v[n];
    //il luam pe elementul N cu 1 si facem dinamica pana la N-2
    for(i=3;i<=n-2;i++)
    {
        d1[i] = max(d1[i-1],v[i]+v[i-1]+d1[i-3]);
    }
    //il putem lua pe elementul 2 impreuna cu elementul 1 si facem dinamica pana la N-1
    for(i=2;i<=n-1;i++)
    {
        d2[i]=max(d2[i-1],v[i]+v[i-1]+d2[i-3]);
    }
    //il putem lua pe elementul 3 impreuna cu elementul 2 si facem dinamica pana la N
    for(i=3;i<=n;i++)
    {
        d3[i]=max(d3[i-1],v[i]+v[i-1]+d3[i-3]);
    }
    sol = max(d1[n-2],d2[n-1]);
    sol = max(sol,d3[n]);
    fout << sol << "\n";
}