Cod sursa(job #3039436)

Utilizator caracioni_octavianCaracioni Octavian caracioni_octavian Data 28 martie 2023 16:09:36
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define NMAX 100003

using namespace std;

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

int dp[NMAX], a[NMAX], N;

int solve(int l, int r) {
    if (r - l + 1 <= 1)
        return 0;

    memset(dp, 0, sizeof(int) * (NMAX - 2));
    dp[2] = a[l] + a[l + 1];
    for (int i = 3; i <= r - l + 1; i++) {
        int ind = i + l - 1;
        dp[i] = max(dp[i - 1], dp[i - 3] + a[ind] + a[ind - 1]);
    }

    return dp[r - l + 1];
}

int main() {

    fin >> N;
    for (int i = 1; i <= N; i++) {
        fin >> a[i];
    }

    fout << max(max(a[1] + a[2] + solve(4, N - 1), a[1] + a[N] + solve(3, N - 2)), solve(2, N));


    return 0;
}