Ciao a tutti, ho vorrei avere un chiarimento su un codice che ho scritto per Sushi variegato.
ho scritto un codice utilizzando prima dei vector di tipo int, poi di tipo long long, nel primo caso ottengo circa 50 punti, nell’altro 100. I vector in questione sono dp e ps.
Il punto è che non penso che il problema sia l’overflow, perchè gestisco bene il modulo in ogni operazione. (o almeno così penso)
Qualcuno riesce a capire come mai il primo codice con int non da 100/100? grazie mille
Ecco il mio codice:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int taglia(int N, int V[]){
vector<int>dp(N + 1, 0); dp[0] = 1;
vector<int>ps(N + 2, 0); ps[1] = 1;
// se le metto long long ottengo 100
unordered_map<int, int>lastocc;
lastocc.reserve(2 * N);
int start = 0;
for(int i = 1; i < N + 1; i++){
int el = V[i - 1];
int npos = 0;
if(lastocc.find(el) != lastocc.end()) npos = lastocc[el] + 1;
start = max(start, npos);
dp[i] = (ps[i] - ps[start]) % MOD; // sum(i - 1, start);
ps[i + 1] = (ps[i] + dp[i]) % MOD;
lastocc[el] = i - 1;
}
return dp[N];
}