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?
Auto comment: topic has been updated by abhi49 (previous revision, new revision, compare).
2D array (with vector) should be very slow. You can rewrite it with 1D array (because
dp[j]
depends only ondp[j-1]
).You can have
dp[-1]
here.