abhi49's blog

By abhi49, history, 4 years 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?

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by abhi49 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

vector<vector >dp(1e3,vector(1e5+1));

2D array (with vector) should be very slow. You can rewrite it with 1D array (because dp[j] depends only on dp[j-1]).

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]);

You can have dp[-1] here.