Cod sursa(job #2578240)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 10 martie 2020 19:34:52
Problema Oo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int v[100001], dp1[100001], dp2[100001], dp3[100001];

int main() {
    in >> n;
    for (int i = 1; i <= n; ++i)
        in >> v[i];
    int rez = 0;
    dp1[2] = v[1] + v[2];
    for (int i = 3; i < n; ++i) {
        dp1[i] = v[i - 1] + v[i];
        for (int j = 2; j <= i - 3; ++j) {
            dp1[i] = max(dp1[i], dp1[j] + v[i - 1] + v[i]);
            rez = max(rez, dp1[i]);
        }
    }
    dp2[3] = v[2] + v[3];
    for (int i = 4; i <= n; ++i) {
        dp2[i] = v[i - 1] + v[i];
        for (int j = 3; j <= i - 3; ++j) {
            dp2[i] = max(dp2[i], dp2[j] + v[i - 1] + v[i]);
            rez = max(rez, dp2[i]);
        }
    }
    dp3[1] = v[1] + v[n];
    for (int i = 4; i <= n; ++i) {
        dp3[i] = v[i - 1] + v[i];
        for (int j = 4; j <= i - 3; ++j) {
            dp3[i] = max(dp3[i], dp3[j] + v[i - 1] + v[i]);
            rez = max(rez, dp3[i]);
        }
    }
    return out << rez, 0;
}