Police 4 80/100

Aiuto
1

sto provando a ottenere 100/100 in police4 ma non riesco a passare l’ultima subtask in quanto il vettore di memo supera i limiti di memoria. Qualche consiglio?

Condivido il mio codice:

#include <bits/stdc++.h>

using namespace std;

// input data
int N, R, T, L;
vector<int> X;
vector<vector<vector<int>>> memo;

int scappa(int idx, int r, int t) {
    if (idx == N) {
        return 0;
    }
    if (r >= N - idx) {
        return L - X[idx];
    }
    t = t % (T * 2);

    if (memo[idx][r][t] != -1) {
        return memo[idx][r][t];
    }

    bool rosso = (t >= T);

    int time1 = X[idx + 1] - X[idx];
    if (!rosso) {
        memo[idx][r][t] = scappa(idx + 1, r, (t + time1) % (T * 2)) + time1;
    } else {
        int time2 = time1 + (2 * T - t);
        if (r > 0) {
            memo[idx][r][t] = min(scappa(idx + 1, r - 1, (t + time1) % (T * 2)) + time1,
                                   scappa(idx + 1, r, (t + time2) % (T * 2)) + time2);
        } else {
            memo[idx][r][t] = scappa(idx + 1, r, (t + time2) % (T * 2)) + time2;
        }
    }
    return memo[idx][r][t];
}

int main() {
    cin.tie(0),cin.sync_with_stdio(0),cout.tie(0),cout.sync_with_stdio(0);

    cin >> N >> R >> T >> L;
    X.resize(N + 1);
    for (int i = 0; i < N; i++)
        cin >> X[i];
    X[N] = L;

    memo.assign(N + 1, vector<vector<int>>(R + 1, vector<int>(2 * T, -1)));

    cout << scappa(0, R, X[0]) + X[0] << endl; 
    return 0;
}
2

Prova a scrivere la stessa idea con un approccio bottom-up, fatto quello è semplice è facile risparmiare memoria