Hello, I am currently doing this question: https://mirror.codeforces.com/contest/837/problem/D
And I need some help. I came up with a good dp algorithm myself:
dp[i][j][k] means the maximum exponent of prime factor 2 we can achieve when we:
choose from the first i integers in a
choose a subset of length j from the first i integers
the exponent of 5 is at most k
then, dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-cur_exp5] + cur_exp2)
note dp[0][0][0] = 0 (don't have to initialize anything)
And implemented this algorithm in Python:
However, this code WAs for test case 8, with my answer of 11 being higher than the expected answer of 9. I have read the editorial for this question, and I believe the DP formula in the editorial is the same as my DP formula mentioned above (please correct me if I am wrong). Therefore, because I believe I have the DP formula correct, I am really confused on why this code still WAs. I know asking people to debug a code is sometimes annoying but I really tried everything and could not figure out why this code is not working, and I would really appreciate it if anyone could tell me why.
Thank you so much!
