Ciao a tutti, stavo risolvendo Calcio (Terry) utilizzando una matrice con le somme prefisse, ma non riesce a risolvere il sesto caso di test in tempo e non riesco a capire perché sia così lento dato che in questo post sul forum (TLE in Calcio (Territoriali)) viene detto che una soluzione con complessità O(NM) dovrebbe andare bene, sbaglio o anche la mia soluzione ha complessità O(NM)?
#include <iostream>
#include <vector>
using namespace std;
int CalcolaDeforestazione(int y, int x, vector<vector<int>> somme_prefisse, int A, int B){
int deforestazione;
deforestazione=somme_prefisse[y+A][x+B]+somme_prefisse[y][x]-somme_prefisse[y+A][x]-somme_prefisse[y][x+B]; //per sapere quanti alberi ci sono in un generico rettangolo di lati A (verticale) e B (orizzontale) con un vertice in (x,y) (quindi il vertice opposto sarà (x+B-1,y+A-1) dato che i vertici sono entrambi compresi (non è come sul piano cartesiano)) basta sottrarre al numero di alberi del rettangolo con vertici 0,0 e x+B-1,y+A-1 il numero di alberi dei rettangolo di vertici 0,0 x-1,y+A-1 e il numero di alberi del rettangolo con vertici 0,0 x+B-1,y-1 e poi aggiungere il numero di alberi del rettangolo con vertici 0,0 x-1,y-1 che è stato sottratto 2 volte perché è un sottoinsieme di entrambi i rettangoli che abbiamo sottratto
return deforestazione;
}
void solve(int t) {
int N, M, K, A, B, x, y, min=-1;
cin >> N >> M >> K >> A >> B;
vector<vector<int>> somme_prefisse(N+1, vector<int>(M+1,0)), mappa(N, vector<int>(M,0)); //somme_prefisse[i][y] contiene il numero totale di alberi nel rettangolo con i vertici opposti in mappa[0][0] e mappa[i-1][y-1]
for (int i=0; i<K; i++){
cin >>x >>y;
mappa[x][y]+=1;
}
for(int y=1; y<=N; y++){
for(int x=1; x<=M; x++){
somme_prefisse[y][x]=somme_prefisse[y][x-1]+somme_prefisse[y-1][x]-somme_prefisse[y-1][x-1]+mappa[y-1][x-1]; //(alberi nel rettangolo con vertici opposti in 0,0 e x,y)=(alberi nella linea che va da 0,y a x-1,y)+(alberi nella linea che va da x,0 a x,y-1)+(alberi nel rettangolo con vertici opposti in 0,0 e x-1,y-1)+(alberi nella casella x,y), dato che le due linee si possono considerare rispettivamente come (alberi nel rettangolo con vertici opposti in 0,0 e x-1,y)-(alberi nel rettangolo con vertici opposti in 0,0 e x-1,y-1) e (alberi nel rettangolo con vertici opposti in 0,0 e x,y-1)-(alberi nel rettangolo con vertici opposti in 0,0 e x-1,y-1) l'equazione si può semplificare a (alberi nel rettangolo con vertici opposti in 0,0 e x,y)=(alberi nel rettangolo con vertici opposti 0,0 e x-1,y)+(alberi nel rettangolo con vertici opposti 0,0 e x,y-1)-(alberi nel rettangolo con vertici opposti in 0,0 e x-1,y-1)+(alberi nella casella x,y)
//nella linea di codice precedente (alberi nella casella x,y) è scritto come mappa[y-1][x-1] perché x e y vanno da 1 a N o M invece di da 0 a N-1 o M-1 perché somme_prefisse ha indice di inizio 1 (somme prefisse[i][j] è sempre uguale a 0 per ogni i e j tali che almeno uno di essi sia uguale a 0)
}
}
for(int y=0; y<=N-A; y++){
for(int x=0; x<=M-B; x++){
int alberi=CalcolaDeforestazione(y,x,somme_prefisse, A, B);
if(alberi<min||min==-1){
min=alberi;
}
}
}
cout << "Case #" << t << ": " << min << "\n";
}
int main() {
#pragma GCC diagnostic ignored "-Wunused-result"
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}
EDIT: Potrebbe forse centrare il fatto che io abbia usato replit per eseguire il codice?