Cod sursa(job #2422329)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 18 mai 2019 13:19:51
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;

int dp[1 + MAX_N];
int a[1 + MAX_N];
int sol;

void solve (int l, int r, int w1, int w2) {
    int rez = a[w1] + a[w2];
    memset (dp, 0, sizeof (dp));
    dp[l - 2] = rez;
    for (int i = l + 1; i <= r; i++) {
        if (i > 3)
            dp[i] = max (dp[i - 3] + a[i] + a[i - 1], dp[i]);
        if (i > 4)
            dp[i] = max (dp[i - 4] + a[i] + a[i - 1], dp[i]);
        if (i > 5)
            dp[i] = max (dp[i - 5] + a[i] + a[i - 1], dp[i]);
        rez = max (rez, dp[i]);
    }
    sol = max (rez, sol);
}

int main() {
    freopen ("oo.in", "r", stdin);
    freopen ("oo.out", "w", stdout);
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sol = 0;

    solve (3, n - 2, 1, n);
    solve (4, n - 1, 1, 2);
    solve (5, n, 2, 3);
    solve (6, n, 3, 4);

    cout << sol << "\n";
    return 0;
}