# Working on a DP problem

I was working on this problem, https://usaco.guide/gold/knapsack#problem-cf-837D. I have the right approach and it is listed in the editorial for the problem. The thing is that I am having some difficulties implementing my solution. I was hoping that you guys could tell me what’s wrong with my solution.

Implementation
#include <bits/stdc++.h>
using namespace std;

const int mxn=201;
long long n,K,num2[mxn],num5[mxn],dp[mxn][mxn],a[mxn],ans;

void calc(int num, int i){
while(num%5==0)
num/=5,num5[i]++;
while(num%2==0)
num/=2,num2[i]++;
}

int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> K;
for(int i=1;i<=n;i++)
cin >> a[i],calc(a[i],i);
for(int i=0;i<n;i++){
for(int j=0;j<K;j++){
for(int k=0;k<=5950;k++){
if(j>i) break;
dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
dp[i+1][j+1][k+num5[i+1]]=max({dp[i][j][k]+num2[i],dp[i+1][j+1][k+num5[i]]});
}
}
}
for(long long i=1;i<=6000;i++)
ans=max(ans,min(i,dp[n][K][i]));
cout << ans;
}


void calc(int num, int i){
while(num%5==0)
num/=5,num5[i]++;
while(num%2==0)
num/=2,num2[i]++;
}


Might integer overflow be occurring in this function? num is passed in as in int.

I can change that. But the thing is that the solution isn’t even passing the base cases.

Then perhaps compare your DP arrays to those of the solutions. The bug might be in your transitions.

I can’t really compare as there is no official implementation as far as I can tell. Also, the solutions other users have used only use 2-d arrays.

Well, it’s only the sample cases. They should be pretty easy to debug, no?