Cod sursa(job #3160344)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 23 octombrie 2023 19:06:08
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 100003;
int dp[NMAX], a[NMAX];

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

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

    return dp[r];
}

int main() {

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

    int res = max(max(a[1] + a[2] + solve(4, n - 1), a[n] + a[1] + solve(3, n - 2)), a[n - 1] + a[n] + solve(2, n - 3));
    fout << res;


    return 0;
}