How did the solution get accepted by adding just this line ?

Revision en1, by Kar98k, 2019-06-21 15:10:50

https://codeforces.me/problemset/problem/498/B

For the above question, this was my TLE solution : 55865422 : time=1000ms

and this was my Accepted solution : [submission:55865596] : time=155ms

In TLE solution, i just added one line: if( dp[i][j] < (1e-12) ) dp[i][j]=0;

and it got accepted.

I am not able to understand that how this one line is able to reduce the time complexity ( and also by such huge margin ) as it is not involved in any of the loops.

Tags #2d-dp, time complexity, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Kar98k 2019-06-21 15:30:42 26 Tiny change: 'ime=1000ms\n\n and this ' -> 'ime=1000ms and this '
en2 English Kar98k 2019-06-21 15:21:30 131
en1 English Kar98k 2019-06-21 15:10:50 614 Initial revision (published)