Getting TLE in one test case

help
,
1

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

test case
test case814×591 41.4 KB

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

2

You can check out mine solution here

1 Like
3

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

4

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

5

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??

6

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

1 Like
7

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
8

okay. got it

9

Thanks everyone for helping…

1 Like
10

Wait - did that actually fix it?

1 Like
11

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
12

Did you get it to work with the recursive approach?

2 Likes
13

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

14

Hey WHy the Pick non pick logic gives RE for few TC
my solution