### himanxu_05's blog

By himanxu_05, 10 days ago,

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;
}

• -1

 » 10 days ago, # |   0 You should always link the problem when asking for help and also describe your approach because it helps others understand your code.That said, I think the tle is probably because the judge is too slow.Other than running an iterative solution, you could try to optimise memory (look up alternating row trick). But I am not sure this would necessarily help you pass the time limit.
 » 10 days ago, # |   0 Try writing iterative solution
 » 10 days ago, # |   0 You should exchange the dimensions to avoid cache misses since we have to do 10^8 operations in 1 second(which is large enough).You can refer to one of the comments regarding TLE in this blog:https://codeforces.com/blog/entry/70018