How can I avoid TLE in this code in c++?

it's counting sum of sub matrix: It works on every test except on last one.

#include <stdio.h>
int main() {
      int a[1000][1000],m,n,i,j,d=0,M,N,H,S,s;
      long int k,q;
      scanf("%d%d",&m,&n);
      for(i=0;i<m;i++)

        for(j=0;j<n;j++)

           scanf("%d",&a[i][j]);

      scanf("%d",&q);
      for(k=1;k<=q;k++)
      {
          s=0;
          scanf("%d%d%d%d",&N,&M,&S,&H);
          for(i=M;i<=M+H-1;i++)
            for(j=N;j<=N+S-1;j++)
               s+=a[i][j];
        printf("%d\n",s);

      }

[Walter Roberson]

Missing closing } corresponding to opening the function

Answer 1

[BhaTTa]

To avoid a Time Limit Exceeded (TLE) error in your code, you need to optimize the way you calculate the sum of submatrices. The current approach of iterating over each submatrix for every query can be inefficient, especially for large matrices and numerous queries. Instead, you can use a technique called prefix sums to preprocess the matrix, allowing you to compute the sum of any submatrix in constant time.Steps to Optimize Using Prefix Sums

1. Preprocess the Matrix:

• Compute a prefix sum matrix where each element at position (i, j) contains the sum of all elements from the top-left corner (0, 0) to (i, j).

2. Compute Submatrix Sum Using Prefix Sums:

• For each query, use the prefix sum matrix to calculate the sum of the submatrix efficiently.

Implementation in C++

Here's how you can implement this optimization:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> a(m, vector<int>(n));
    vector<vector<long long>> prefixSum(m + 1, vector<long long>(n + 1, 0));

    // Input the matrix
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            // Build the prefix sum matrix
            prefixSum[i + 1][j + 1] = a[i][j] + prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j];
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int N, M, S, H;
        cin >> N >> M >> S >> H;

        // Adjust for 0-based index
        N--; M--;

        // Calculate the sum of the submatrix using the prefix sum matrix
        long long s = prefixSum[M + H][N + S] - prefixSum[M][N + S] - prefixSum[M + H][N] + prefixSum[M][N];
        
        cout << s << endl;
    }

    return 0;
}