Followed exact logic in the hint video, it gives TLE in the second case

#1
#2

hi @Arpan_Goswami,

don’t use !dp[i][j] in your for condition as it is useless, as dp[I][j] is initialized with false and !dp[I][j] will always be true, it adds to your computation and increases time , especially in this question as constraints are very tight
for(int j=1;j<=sum && !dp[i][j];j++){

corrected code :-

In case of any doubt feel free to ask :slight_smile:
Mark your doubt as RESOLVED if you got the answer

#3

Still gives TLE after making those desired changes

#4

I submitted many times in succession. On one of the attempts the code miraculously got accepted. I think the coding blocks admin team need to modify the second test case so that such inconsistencies are weeded out. I have submitted the same code and have got varying result of accepted and TLE on the second test case. If this is the case with bottom up dp,I am pretty sure the top down dp solution will never get accepted.

#5

Also changing vector to dynamically allocated arrays does the trick.

#6

yeah! i agree with you, the constraints were very strict, will mention about correction in test case 2

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.