After TLE'ing this problem in the contest I've been unable to come up with a satisfactory explanation as for why it does so. The mystery is why does my solution behave so much worse on case 65 than any of the other previous max sized cases. Since I cannot clearly see a reason why I feel it's possible this could happen again. I'm not looking for suggestions on how to make my code faster.
My solution is listed at http://codeforces.com/contest/498/submission/9250377
I've noticed other solutions that did manage to pass using essentially the same algorithm are also significantly slower on case 65 than any of the other cases. For example http://codeforces.com/contest/498/submission/9251777
Link to problem — http://codeforces.com/problemset/problem/498/B
I mentioned the same thing here: http://codeforces.com/blog/entry/15353#comment-202844
I also TLE'd on test case 65.
This may or may not be relevant, but I remember a similar thing happening in a topcoder round. You can see the thread here: http://apps.topcoder.com/forums/?module=Thread&threadID=708376
TLDR: There are things called "denormal" numbers that take longer to do operations with
Yeah, looks like you're right
Probably, problem is as usual in denormalized numbers.
you may see last my two submissins, I've added if(cur < 1e-12) cur = 0 and my code become 5 times faster
Want to see some magic? Here's your solution with minor changes.
Edit: others already posted about denormalized numbers while I was writing this comment.