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...
#include<bits/stdc++.h>
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