Cod sursa(job #2125370)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 8 februarie 2018 13:37:10
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream>

using namespace std;

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

int DP1[100003],DP2[100003],DP3[100003],N,V[100003];

int main()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        fin>>V[i];
    DP1[1]=0;
    DP1[2]=V[1]+V[2];
    DP1[3]=max(DP1[2],V[2]+V[3]);
    for (int i=4;i<=N-1;i++)
        DP1[i]=max(DP1[i-1],V[i-1]+V[i]+DP1[i-3]);
    DP2[1]=V[1]+V[N];
    DP2[2]=max(DP2[1],V[1]+V[2]);
    DP2[3]=max(V[3]+V[4],DP2[2]);
    for (int i=4;i<=N-2;i++)
        DP2[i]=max(DP2[i-1],V[i-1]+V[i]+DP2[i-3]);
    DP3[1]=0;
    DP3[2]=0;
    DP3[3]=V[2]+V[3];
    for (int i=4;i<=N;i++)
        DP3[i]=max(DP3[i-1],V[i-1]+V[i]+DP3[i-3]);
    fout<<max(max(DP3[N],DP2[N-2]),DP1[N-1]);
}