Cod sursa(job #2943742)

Utilizator NashikAndrei Feodorov Nashik Data 21 noiembrie 2022 16:37:02
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
//#include <iostream>
#include <fstream>
using namespace std;
int d[100005][3],v[100005];
int n;
int main()
{
    ifstream cin("oo.in");
    ofstream cout("oo.out");
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    ///cazul 1 -> luam 1 si n
    ///cazul 2 -> nu luam 1 si n, DAR LUAM 1 2
    ///cazul 2 -> nu luam 1 si n, DAR nu luam 1 2

    ///cazul 1
    ///d[i][0]-->folosind numerele mai mici decat i fara i
    ///d[i][1]-->folosind numerele mai mici decat i cu i
    d[1][1]=v[1]+v[n];

    d[2][0]=d[1][1];
    for(int i=3;i<=n-2;i++){
        d[i][0]=max(d[i-1][0],max(d[i-2][0],d[i-2][1]));
        d[i][1]=max(d[i-2][0]+v[i-1]+v[i],max(d[i-3][0]+v[i]+v[i-1],d[i-3][1]+v[i]+v[i-1]));
    }
    int maxim=0;
    for(int i=1;i<=n;i++)
        maxim=max(maxim,max(d[i][0],d[i][1]));


    ///cazul 2
    for(int i=1;i<=n;i++){
        d[i][0]=0;
        d[i][1]=0;
    }

    d[2][1]=v[1]+v[2];
    for(int i=4;i<=n-1;i++){
        d[i][0]=max(d[i-1][0],max(d[i-2][0],d[i-2][1]));
        d[i][1]=max(d[i-2][0]+v[i-1]+v[i],max(d[i-3][0]+v[i]+v[i-1],d[i-3][1]+v[i]+v[i-1]));
    }
    for(int i=1;i<=n;i++)
        maxim=max(maxim,max(d[i][0],d[i][1]));
    ///cazul 3
    for(int i=1;i<=n;i++){
        d[i][0]=0;
        d[i][1]=0;
    }
    for(int i=3;i<=n;i++){
        d[i][0]=max(d[i-1][0],max(d[i-2][0],d[i-2][1]));
        d[i][1]=max(d[i-2][0]+v[i-1]+v[i],max(d[i-3][0]+v[i]+v[i-1],d[i-3][1]+v[i]+v[i-1]));
    }
    for(int i=1;i<=n;i++)
        maxim=max(maxim,max(d[i][0],d[i][1]));
    cout<<maxim;
    return 0;
}