You are not logged in. Please login at www.codechef.com to post your questions!

×

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: alt text

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)

asked 09 Jan '15, 11:54

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

edited 09 Jan '15, 11:59


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

link

answered 09 Jan '15, 13:28

superty's gravatar image

3★superty
36417
accept rate: 31%

Okay thanks a lot mann :)

(09 Jan '15, 13:34) ketanhwr6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×715
×530
×385
×109
×7

question asked: 09 Jan '15, 11:54

question was seen: 471 times

last updated: 09 Jan '15, 13:34