I was getting TLE for this problem although I was sure that my solution was correct and efficient enough. Accidentally, I changed the below loops

for (int i = N ; i >= 0 ; i --)
    for (int j = M ; j >= 0 ; j --) 
        cable [j][i] = 0 , dp [j][i] = -1 ;

to

for (int i = N ; i >= 0 ; i --)
    for (int j = M ; j >= 0 ; j --) 
        cable [j][i] = 0 ;          
for (int i = N ; i >= 0 ; i --)
    for (int j = M ; j >= 0 ; j --) 
        dp [j][i] = -1 ;

, and, surprisingly, I got Accepted!! Apart from these codes, I have another accepted program, which managed to get Accepted under 2 seconds; however, I cannot find out what makes my programs run sluggishly or fast.

I'm not sure exactly what was going on.

But my guess is, as judge compiles c++ with -O2 switch it does some optimizations. From the OS perspective, it is faster to iterate over the first dimention of an array first and then the second dimention.

You are having a loop over i and j, but you are accessing dp[j][i]. The second code might be optimized by the compiler by swaping the order of the loops which cause it to run faster.

You can try the other way around to see if it is actually matters.

Yeah, worked! One second faster than previous programs!

beginner1010 said:

Yeah, worked! One second faster than previous programs!

Great :D