TIMBER: Runtime Error

I was solving this problem on IARCS Judge: http://opc.iarcs.org.in/index.php/problems/TIMBER

And I made a O(n*m + c) solution but still it says TLE on some cases:

And it says Runtime Error: TLE. Idk whether it is a runtime error or not. Because I don’t think that there is segmentation fault anywhere. Nor there should TLE because O(n*m + c) solution is perfectly fine for the test data.
Here is my code. Can anyone help me find the problem?

``````#include<iostream>
using namespace std;

int dp[1002][1002];
int a[1001][1001];

int main()
{
ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
cin >> a[i][j];
int c;
cin >> c;
dp[1][1] = a[0][0];
for(int i = 0;i <= n;i++) dp[i][0] = 0;
for(int j = 0;j <= m;j++) dp[0][j] = 0;
for(int i = 2;i <= n;i++) dp[i][1] = a[i-1][0] + dp[i-1][1];
for(int i = 2;i <= m;i++) dp[1][i] = a[0][i-1] + dp[1][i-1];
for(int i = 2;i <= n;i++)
for(int j = 2;j <= m;j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1];

//***DEBUG***

/*cout << endl;
for(int i = 0;i < n+1;i++)
{
for(int j = 0;j < m+1;j++)
cout << dp[i][j] << " ";
cout << endl;
}
cout << endl;*/

for(int ctr = 0;ctr < c;ctr++)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;
}
return 0;
}
``````

If anyone is having confusion regarding the approach of my code, then here is the approach: http://www.iarcs.org.in/inoi/contests/dec2004/Advanced-2-solution.php
(The approach is the bottom most pseudocode on this webpage)

1 Like

The code gets accepted if we change cin/cout to scanf/printf. So, it seems that the judge compiler does not optimize the C++ streams due to `ios::sync_with_stdio(false);`

Btw, your code could be much simpler:

``````for(i = 1;i <= n;i++)       // start in 1!
for(j = 1;j <= m;j++)
cin >> a[i][j];
cin >> c;
for(i = 1;i <= n;i++)     // global dp matrix is initialized to zero.
for(j = 1;j <= m;j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i][j];``````
1 Like

Thanks…