Getting TLE in one test case

why i am getting TLE in #5th test case “Minimizing Coins” problem of cses.


problem link CSES - Minimizing Coins
solution link https://cses.fi/paste/b55d263612403c8f27eac8/

You can check out mine solution here

1 Like

Thanks, but can you tell me what’s wrong in my code?

(Not sure) Are you sure there will not be an Integer overflow in your program?

I can’t see any integer overflow.
when i use the #5th test case input then my program never returns.
So, i shortened the input to
2 1000000
649304 85832
then i got this
sdvsvvsvsvsvsvsv
What’s this actually means. Please tell??

Um, I quite don’t understand what you’re getting. Maybe, @ssjgz can help?

1 Like

At a very quick glance before I go to work: you don’t seem to be using memoisation in any meaningful way i.e. each call to recursion works out the answer from scratch instead of checking dp to see if we already know the answer and just returning that. Compare with @dontcheckme 's solution.

This check should be added before the for loop.

Aside from that: no idea :slight_smile:

2 Likes

okay. got it

Thanks everyone for helping…

1 Like

Wait - did that actually fix it?

1 Like

No. not yet. I go through bottom-up approach and then it works. recursion still not working, but i will try till AC…

2 Likes

Did you get it to work with the recursive approach?

2 Likes

Yes.
solution link: https://cses.fi/paste/a44ff1cff13bb43d2a16b9/