So,here is a problem from cses problemset on dynamic programming [Book Shop](https://cses.fi/problemset/task/1158).And i solved it in the complexity of o(n*x) which accroording 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?
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?
