My code (C++) is having worst case complexity of 10^8 (precisely 9*10^7 )and time limit for the question is 3 sec. I am getting TLE, so what should be worst case complexity to pass the test cases.
My code (C++) is having worst case complexity of 10^8 (precisely 9*10^7 )and time limit for the question is 3 sec. I am getting TLE, so what should be worst case complexity to pass the test cases.
Sorry, question is from ongoing codechef long contest.
In that case, try heavy optimization. Of course, if it's not a DP and you mean just that the complexity is like O(N2K) where N ≤ 103 and K ≤ 90, then there can be a big bad constant factor.
Try running your code on your system and check how long it runs on some worst cases.
I checked it on my system it was taking around 4 sec for worst case. But finally i corrected it and got it accepted. :) Thanks BTW.