Aiuto con preoii_treni

Aiuto
1

Ciao a tutti!
Stavo risolvendo preoii_treni (su algobadge) e mi sono ritrovato che nel subtask 5 sforo i limiti di memoria, suppongo a causa della matrice che utilizzo per la memoizzazione.
Il mio codice:

#include<algorithm>
#include<vector>
using namespace std;

//#pragma GCC optimize ("O3")

int trova(const int A[], const int B[], const int &N, const int &i, const int &nTreniPresi, vector<vector<int>> &matMemo){
    if(i==N){
        return 0;
    }
    if(matMemo[i][nTreniPresi]==-1){
        int a=0, b=0, c=0;
        a=trova(A,B,N,i+1,nTreniPresi+1, matMemo)+A[i];
        c=trova(A,B,N,i+1,0, matMemo);
        if(nTreniPresi==0){
            b=trova(A,B,N,i+1,nTreniPresi+1, matMemo)+B[i];
        }
        matMemo[i][nTreniPresi]=max(max(a,b),c);
    }
    return matMemo[i][nTreniPresi];
}

int tempo_massimo(int N, int a[], int b[])
{
    vector<vector<int>> memo(N, vector<int>(N, -1));
    return trova(a, b, N, 0, 0, memo);   
}

Qualcuno saprebbe darmi qualche suggerimento per occupare meno memoria? Es. utilizzare una struttura dati diversa, o ridimensionare la matrice attuale ecc.
Ringrazio in anticipo.

2

ti serve davvero una matrice? inoltre trovo che questo problema sia molto più facile iterativamente.

1 Mi Piace
3

Ciao Zaccaria,
Il tuo ragionamento è in parte giusto.

È una minuzia, ma forse non ci avevi pensato:

nTreniPresi lo incrementi a valori strettamente positivi, e poi quando serve, lo azzeri.

Potresti direttamente sostituire il suo tipo a bool.

Già questo da solo potrebbe risolvere i tuoi problemi di memoria…immagina che ci siano 10^6 giorni, che dimensione avrebbe la matrice?

Se invece la mettessi a bool, avrebbe massimo 2 colonne.

Pensa anceh a quando puoi confrontare le due colonne della matrice e quando no.

2 Mi Piace
4

Grazie mille! Ora ottengo 100/100… con la “minuzia” :grin:
Avevo già pensato in precedenza a ridurre la seconda dimensione della matrice, ma con diversi tentativi l’output mi usciva diverso… Effettivamente non avevo pensato a renderla bool. Con il limite di N=10^6 la matrice occupava da sola circa 3,63 TB, ora bastano 8 MB.
Rispondendo a @Fxby, ero arrivato già ad un approccio iterativo, ma mi portava a un punteggio di 55/100 con 2 testcase errati che mi toglievano i 45 punti, e non ero riuscito ad isolare il caso limite che mi dava l’errore. Ringrazio comunque dei consigli!

5

Il problema si può risolvere in 10 righe di codice iterativamente :new_moon_with_face: