My code is failing 2 out of 13 test cases.
This is the problem: D - Knapsack 1
this is the code:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define endl '\n'
#define x first
#define y second
#define remove erase
#define pb push_back
#define mod1 1000000007
#define mod2 998244353
#define xrange(i,s,n) for(int i=s;i<n;i++)
#define yrange(i,n,s) for(int i=n;i>=s;i--)
#define deb(x) cerr<<'\t'<<#x<<" is "<<(x)<<endl
#define usefile freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define debvec(v) cerr<<#v<<" is [ ";for(auto el:v)cerr<<el<<" ";cerr<<"]\n";
#define debmap(m) cerr<<#m<<" is [ ";for(auto p:m)cerr<<"("<<p.x<<","<<p.y<<") ";cerr<<"]\n";
#define tezz int32_t main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;}
#define tezzn int32_t main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int32_t t;cin>>t;while(t--)solve();return 0;}
using namespace std;
// . . . S O L U T I O N . . . B E G I N S . . . F R O M . . . H E R E . . .
int dp[100000][100];
int knapsack (int wt[], int pr[], int w, int n) {
if (w == 0 || n == 0) return 0;
if (dp[w][n] != -1) return dp[w][n];
int currwt = wt[n-1], currpr = pr[n-1];
if (w < currwt) return dp[w][n] = knapsack(wt, pr, w, n-1);
else return dp[w][n] = (max(knapsack(wt, pr, w, n-1), currpr + knapsack(wt, pr, w-currwt, n-1)));
}
void solve () {
int n, w;
memset(dp, -1, sizeof dp);
cin >> n >> w;
int wt[n], pr[n];
xrange(i, 0, n) cin >> wt[i] >> pr[i];
cout << knapsack(wt, pr, w, n) << endl;
}
tezz
