I am not able to solve cses book shop problem using recursive method as i am getting TLE. I am not that good in iterative method can somebody tell me what is wrong and how to prevent it. Below is my code
#include <bits/stdc++.h>
int n , x;
int h[1001] , s[1001];
const int mxn = 1e5 + 1;
int dp[1001][mxn];
int rec(int lvl ,int capa) {
if (lvl == n) return 0;
if (capa > x) return 0;
if(dp[lvl][capa] != -1) return dp[lvl][capa];
int ans {};
ans = rec(lvl + 1, capa);
// ans = INT_MIN;
if (capa + h[lvl] <= x) {
ans = std::max(ans , s[lvl] + rec(lvl + 1, capa + h[lvl]));
}
return dp[lvl][capa] = ans;
}
int main() {
std::cin >> n >> x;
memset(dp,-1,sizeof(dp));
for (int i = 0 ; i < n ; i++) {
std::cin >> h[i];
}
for (int i = 0 ; i < n ;i++) {
std::cin >> s[i];
}
std::cout << rec(0,0);
return 0;
}
