Cod sursa(job #2570697)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 4 martie 2020 18:39:16
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

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

int oua[100005];
int DP0[100005], DP1[100005], DP2[100005];
const int inf = 1000000004;

int main()
{
    int n,i,sol = 0;
    fin>>n;
    for(i = 1; i <= n; i++){
        fin>>oua[i];
    }
    if(n == 2){
        fout<<oua[1] + oua[2];
        return 0;
    }
    /**daca il iau pe 1*/ // => ca pe n voi lua doar DP0
    DP0[1] = -inf; //imposibil sa le iau si sa nu le iau in acelasi timp
    DP1[1] = oua[1]; //suma oualor pana la 1 e cat am luat din 1
    DP2[1] = -inf; // imposibil sa fie si luate prin lacomie si sa fie si luate normal
    for(i = 2; i <= n; i++){
        DP0[i] = max(DP0[i-1],DP2[i-1]);
        DP1[i] = DP0[i-1] + oua[i];
        DP2[i] = DP1[i-1] + oua[i];
    }
    sol = max(sol,DP0[n]);
    /**daca il iau lacom pe 1*/ // => am luat normal pe n => iau doar DP1[n]
    DP0[1] = -inf; // imposibil sa le si iau si sa le las in pace
    DP1[1] = -inf; // imposibil sa le iau lacom daca le iau normal
    DP2[1] = oua[1]; // posibil si iau lacom doar ce ma pe 1
    for(i = 2; i <= n; i++){
        DP0[i] = max(DP0[i-1],DP2[i-1]);
        DP1[i] = DP0[i-1] + oua[i];
        DP2[i] = DP1[i-1] + oua[i];
    }
    sol = max(sol,DP1[n]);
    /**daca nu iau din 1 nimic*/ // => pot lua fie DP2[n], fie DP0[n];
    DP0[1] = 0;
    DP1[1] = -inf;
    DP2[1] = -inf;
    for(i = 2; i <= n; i++){
        DP0[i] = max(DP0[i-1],DP2[i-1]);
        DP1[i] = DP0[i-1] + oua[i];
        DP2[i] = DP1[i-1] + oua[i];
    }
    sol = max(sol,max(DP0[n],DP2[n]));
    fout<<sol;
    return 0;
}