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

3 次查看（过去 30 天）
Una Jacimovic
Una Jacimovic 2018-7-17
评论： Walter Roberson 2024-9-6
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);
}

请先登录，再回答此问题。

回答（1 个）

BhaTTa
BhaTTa 2024-9-6
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;
}

类别

在 Help Center 和 File Exchange 中查找有关 MATLAB 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by