Cod sursa(job #3275817)

Utilizator mihai_bosIancu Mihai mihai_bos Data 11 februarie 2025 19:58:05
Problema Oo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int MAX_N = 100001;
int n, v[MAX_N], dp1[MAX_N], dp2[MAX_N];

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

    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];

    if (n == 2) {
        fout << v[1] + v[2] << "\n";
        return 0;
    }

    // Caz 1: excludem ultimul sector (lucrăm pe [1, N-1])
    dp1[1] = 0;
    dp1[2] = v[1] + v[2];
    for (int i = 3; i <= n - 1; ++i) {
        dp1[i] = max(dp1[i - 1], v[i] + v[i - 1] + (i >= 3 ? dp1[i - 3] : 0));
    }

    // Caz 2: excludem primul sector (lucrăm pe [2, N])
    dp2[2] = 0;
    dp2[3] = v[2] + v[3];
    for (int i = 4; i <= n; ++i) {
        dp2[i] = max(dp2[i - 1], v[i] + v[i - 1] + (i >= 4 ? dp2[i - 3] : 0));
    }

    fout << max(dp1[n - 1], dp2[n]) << "\n";
    return 0;
}