Aiuto con calcio 6/16

[Elisa335]

import java.util.*;
import java.io.*;
import java.lang.*;

public class calcio {
    public int solve(int N, int M, int K, int A, int B, int[] X, int[] Y) {
        
        

        int [][] foresta = new int [N] [M];
        ArrayList<Integer> alberi = new ArrayList<>();
        for (int i = 0; i < X.length; i++) {
            foresta[X[i]][Y[i]] += 1;
        }

        
        int b = N-A;
        while (b>=0) {
            int a = M-B;
            
            while (a >= 0) {
                int c = 0;
        
                for (int i = 0+b; i < A+b; i++) {
                    for (int j = 0+a; j < B+a; j++) {
                        c += foresta[i][j];
                    }            
                }
                alberi.add(c);
                a--;
        }
            b--;
        }

        int r = alberi.get(0);
        
        for (Integer i : alberi) {
            if (i<r){
                r = i;
            }
        }      
        
        int risposta = r;

        return risposta;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException {
        // se preferisci leggere e scrivere da file
        // ti basta modificare la seguente variabile
        boolean input_from_file = true;

        InputStream fin;
        OutputStream fout;
        if(input_from_file) {
            fin = new FileInputStream("input.txt");
            fout = new FileOutputStream("output.txt");
        } else {
            fin = System.in;
            fout = System.out;
        }

        Scanner scn = new Scanner(fin);
        PrintStream prnt = new PrintStream(fout);

        int T = scn.nextInt();
        for(int t = 1; t <= T; t++) {
            int N = scn.nextInt();
            int M = scn.nextInt();
            int K = scn.nextInt();
            int A = scn.nextInt();
            int B = scn.nextInt();

            int[] X = new int[K];
            int[] Y = new int[K];

            for (int i = 0; i < K; i++) {
                X[i] = scn.nextInt();
                Y[i] = scn.nextInt();
            }

            calcio solver = new calcio();
            int risposta = solver.solve(N, M, K, A, B, X, Y);

            prnt.format("Case #%d: %d\n", t, risposta);
            fout.flush();
        }
    }
}

Ciao a tutti, vorrei sapere come potrei fare a velocizzare l’esecuzione del codice, perché alla fine la matrice diventerebbe di 7000^2 ed anche se il codice è corretto dopo il sesto test case non riesco più ad andare avanti per i dati molto grandi.
Grazie mille a tutti in anticipo

Questo è il testo e l’obiettivo del problema:

[Mazza7]

L’idea è di creare una matrice di somme prefisse, in modo da calcolare il numero di alberi in tempo costante.

Hint

Puoi farlo salvando in ogni casella il numero di alberi che contiene il “rettangolo” con l’inizio.
Poi calcolare il numero di alberi di un campo da calcio sapendo i valori dei suoi estremi.
(se serve mando il codice … anche se è in c++)

[Elisa335]

Sì, grazie mi sarebbe d’aiuto il codice.
Perché non ho capito pienamente il tuo ragionamento

[Elisa335]

Più che altro non ho capito che cosa intendi con una matrice di somme prefisse

[Mazza7]

Questo è il codice:

#include <iostream>
#include <vector>
#include <cmath>
#define maxnm 7000
using namespace std;

int foresta[maxnm][maxnm];

void solve(int t) {
    int N, M, K, A, B;
    cin >> N >> M >> K >> A >> B;

    for(int i=0;i<N;i++){ //inizializzo la matrice
    	for(int j=0;j<M;j++){
    		foresta[i][j]=0;
		}
	}

    for (int i = 0; i < K; i++) { //prendo l'input
    	int tempx,tempy;
        cin >> tempx >> tempy;
        foresta[tempx][tempy]+=1;
    }
    for(int i=1;i<N;i++){ //costruisco la prima colonna
    	foresta[i][0]+=foresta[i-1][0];
	}
	
	for(int i=1;i<M;i++){ //costruisco la prima riga
		foresta[0][i]+=foresta[0][i-1];
	}
	
	for(int i=1;i<N;i++){ //costruisco il resto
		for(int j=1;j<M;j++){
			foresta[i][j]+=(foresta[i-1][j]+foresta[i][j-1]-foresta[i-1][j-1]); //aggiungo la casella sopra e quella a lato, tolgo la parte contata due volte
		}
	}
	int minimo=A*B; //potrebbe essere troppo basso ... nel caso 1e9 dovrebbe andare
	for(int i=A-1;i<N;i++){
		for(int j=B-1;j<M;j++){
			int temp=foresta[i][j]; //angolo più in basso
			if(i>=A) temp-=foresta[i-A][j]; //se serve tolgo le colonne in più
			if(j>=B) temp-=foresta[i][j-B]; //se serve tollgo le righe in più
			if(i>=A && j>=B ) temp+=foresta[i-A][j-B]; //aggiungo la parte che ho tolto due volte
			minimo=fmin(minimo,temp);
		}
	}
	
    cout << "Case #" << t << ": " << minimo << "\n";
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("calcio_input_1.txt", "r", stdin);
    //freopen("output_1.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}

Edit : no so perché t partisse da 6

[Mazza7]

Ti spiego come funziona:

• In ogni casella della matrice salvi il numero di alberi nel “rettangolo” da quella casella fino all’inizio
• Puoi farlo aggiungendo le due caselle “prima” che hai già calcolato (cioè quella sopra e quella a sinistra) togliendo quella di uno sopra in diagonale perché quell’area l’hai contata due volte
• Ora hai in ogni casella il numero degli alberi, quindi per calcolare un campo da calcio ti basta togliere quello che non è compreso. (ricordandoti di risommare quello che togli due volte)

Forse così è più comprensibile