Take the 2-minute tour ×

The question is as follows

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.


    3   8

  8   1   0

2   7   4   4

4 5 2 6 5 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

I had the following error

Your program had this runtime error: Bad
syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think
this is wrong]. The program ran for 0.259 CPU seconds before the
error. It used 16328 KB of memory.

The code is as follows.

int arr[1500][1500];
map < int,map < int,int> >dp;

int main()
    // ofstream fout ("numtri.out");
    // ifstream fin ("numtri.in");
    int n;
    // fin>>n;
    freopen ("numtri.in", "r", stdin);
    freopen ("numtri.out", "w", stdout);
    scanf ("%d", &n);
    int ct = 1;
    int gaga = -100;
        for (int j=0; j<ct; j++)
            scanf ("%d", &arr[i][j]);
                dp[i][j] = maxi (dp[i-1][j-1] + arr[i][j], dp[i-1][j] + arr[i][j]);
            if (i == n-1)
                if (dp[i][j] > gaga)
    printf ("%d\n", gaga);
    return 0;

It works fine on my laptop. On the website it works for 8 test cases and fails for 9th one with this error.

Thanks for the help!

share|improve this question
add comment

1 Answer


You check if i > 0, which will ensure you never access a negative index. You never do the same for j however, so you will access dp[i-1][-1] on the first run of the inner (j) loop. I'm pretty sure this is what causes the error.

share|improve this answer
+1 This seems most likely. Usually DP solutions start by initializing corner cases, and then continue iterating from the next item (in this case, both for loops should start at 1), which avoids the need to check index values on each iteration. I also don't know why dp is map, instead of being a plain array. –  Groo Mar 15 '12 at 12:20
I used a map so that all negative indices will be zero and i dont need to take care of it.. –  Zer0 Mar 15 '12 at 18:05
add comment

Your Answer


