Per il testo calcio:
int foresta[MAX][MAX],pref_sum[MAX][MAX],sli_win[MAX][MAX];
void solve(int t) {
int N, M, K, A, B;
cin >> N >> M >> K >> A >> B;
int X, Y;
for (int i = 0; i < K; i++) {
cin >> X >> Y;
foresta[X][Y] += 1;
}
int mini = K+1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
pref_sum[i][j] = foresta[i][j] + pref_sum[i - 1][j] + pref_sum[i][j - 1] - pref_sum[i - 1][j - 1];
if(i >= A-1 && j>= B-1){
sli_win[i][j] = pref_sum[i][j] - pref_sum[i-A][j] - pref_sum[i][j-B] + pref_sum[i-A][j-B];
mini = min(mini,sli_win[i][j]);
}
}
}
cout << "Case #" << t << ": " << mini << "\n";
}
ho scritto questo programma sfruttando una sliding window che capisce quanti alberi sono presenti nella finestra basandosi su una matrice di somme prefisse, dai casi base sembra funzionare e nei forum spronano ad usare questa tipologia di approccio, ma inviando la soluzione sono pochi i casi che passano. Il codice sostanzialmente crea una normale matrice di somme prefisse e poi una sliding window calcola quanti alberi ci sono sottraendo le caselle in eccesso e aggiungendo gli elementi che vengono rimossi da entrambe le caselle, infine controlla se il numero di alberi è minore del precedente. Sto per raggiungere tutti gli argento, mi mancherebbero pochi punti ma il 3 luglio chiuderanno le possibilità di essere in classifica.