Favorite_number7's blog

By Favorite_number7, history, 2 months ago, In English

So,here is a problem from cses problemset on dynamic programming Book Shop.And i solved it in the complexity of o(n*x) which according to me should get accepted ,but this is giving TLE on larger test cases. Here is my solution:

Your code here...


using namespace std;

define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

vector<vector<int> >dp(1e3,vector<int>(1e5+1)); int main() { #ifndef ONLINE_JUDGE freopen("input1.txt","r",stdin); freopen("output.txt","w",stdout); #endif fastio; int test_case; test_case=1; while(test_case--){ int n,x,i,j,t; cin>>n>>x; vector<int> v1(n),v2(n); for(auto &ele:v1){ cin>>ele; } for(auto &ele:v2){ cin>>ele; } for(i=0;i<=x;i++){ for(j=0;j<n;j++){ if(v1[j]<=i){ if(j==0&&v2[j]>dp[j][i]){ dp[j][i]=v2[j]; } else{ dp[j][i]=max(v2[j]+dp[j-1][i-v1[j]],dp[j-1][i]); } } else if(j!=0&&dp[j][i]<dp[j-1][i]) dp[j][i]=dp[j-1][i]; } }
cout<<dp[n-1][x]<<endl; } }

Can anyone tell me where am i going wrong?

Read more »

  • Vote: I like it
  • +9
  • Vote: I do not like it