TIMBER: Runtime Error

general
, , , ,
1

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)

2

It is not Runtime Error, it’s actually TLE.

Your algorithm is correct, but you need to take care of some implementation details:

  1. Don’t use endl. It’s slow because it not only outputs new line but flushes the output as well. Just use ‘\n’.
  2. Do use cin.tie(0) at the start of the program. cin.tie(0) basically tells the program not to output immediately when you tell it to. Well, sort of, I’m not really sure but anyways the end result is that your program runs faster, but the output and input may not come out in the same order that you expect. This is never a problem when submitting but it may cause confusion if you are trying to debug. Just comment it out unless you’re submitting to the judge. Also don’t use this in interactive problems because you actually need to print the output before you get the input in that case.
  3. Otherwise, if you don’t want to do 1 and 2, you could always just use scanf and printf. I notice you’re using ios::sync_with_stdio to speed up cin/cout, cin.tie(0) just speeds it up more but scanf/printf doesn’t need to be sped up.

Here’s the Accepted code: http://pastebin.com/nMNtmtLK

1 Like
3

Okay thanks a lot mann :slight_smile: