Code : Earn or Unlock

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    // dp[i][j] is the maximum profit on the suffix a[i...] when the greatest
    // unlocked index is j.

    // Last element can only be used for victory points.
    dp[n - 1][n - 1] = a[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            // All cards are locked.
            if (j < i) {
                continue;
            }
            // Use a[i] to unlock some cards.
            int up = min(n - 1, j + a[i]);
            dp[i][j] = max(dp[i][j], dp[i + 1][up]);

            // Use a[i] to gain victory points.
            dp[i][j] = max(dp[i][j], a[i] + dp[i + 1][j]);
        }
    }

    cout << dp[0][0] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    solve(a);
}

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<long long> dp(n, 0);
    // dp[j] is the maximum profit of the current suffix when the greatest
    // unlocked index is j.

    // Suffix of 1 element.
    dp[n - 1] = a[n - 1];

    for (int i = n - 2; i >= 0; i--) {
        auto ndp = dp;
        for (int j = 0; j < n; j++) {
            // All cards are locked.
            if (j < i) {
                continue;
            }
            // Use a[i] to unlock some cards.
            int up = min(n - 1, j + a[i]);
            ndp[j] = max(ndp[j], dp[up]);

            // Use a[i] to gain victory points.
            ndp[j] = max(ndp[j], a[i] + dp[j]);
        }
        swap(dp, ndp);
    }

    cout << dp[0] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    solve(a);
}

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> &a) {
    int n = a.size();

    vector<long long> dp(n + n, 0);
    // dp[j] is the maximum profit of the current suffix when the greatest
    // unlocked index is j.

    for (int i = (int)dp.size() - 1; i >= 0; i--) {
        auto ndp = dp;
        for (int j = 0; j < n; j++) {
            // All cards are locked.
            if (j < i) {
                continue;
            }
            // Use a[i] to unlock some cards.
            ndp[j] = max(ndp[j], dp[j + a[i]]);

            // Use a[i] to gain victory points.
            ndp[j] = max(ndp[j], a[i] + dp[j]);
        }
        swap(dp, ndp);
    }

    cout << dp[0] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    solve(a);
}