Master0fPuppets's blog

By Master0fPuppets, history, 5 weeks ago, In English

I was trying to solve this DP problem but it kept giving me TLE and IDK why

My approach is that I go through the array of people and try to find the best value for the ith person and I made a dp array with i which represent the position and j which represent the current weight so the time of this solution would be P*N*W which should work fine but IDK why it doesn't so can you please help me.

Problem: https://vj.ppsucxtt.cn/78a406edbe180405242b17cc54390625?v=1634888252 Solution: https://ideone.com/HwlhXn

Tags dp, tle
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by Master0fPuppets (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

If your solution does $$$P*N*W$$$ work for every test case, then overall you are doing $$$T*P*N*W$$$ operations which is about $$$3*10^9$$$ operations, which will likely TLE on many judges.