#include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <queue> #include <array> #include <cmath> using namespace std; using ll = long long; const int MAXN = 1e5+1; const int MAXW = 2e3+1; void setIO(string name="") { ios_base::sync_with_stdio(0); cin.tie(0); } // naive approach: put k copies of everythign into one vector, run standard 0/1 knapsack // fails on K <= 1e9, // W <= 2000. N*W means that naive 0/1 fails anyways. void solve() { int x,n; cin >> x >> n; map<int,vector<pair<int,int>>> by_w; for (int i=1; i<=n; i++) { int v,w,k; cin >> v >> w >> k; by_w[w].push_back({v,k}); } for (int i=0; i<=n; i++) { } vector<vector<ll>> dp(by_w.size() + 1,vector<ll>(x + 1, INT32_MIN)); // initiliase all values of dp vector as INT32_min dp[0][0]=0; int at=1; // grouped the items by weight, sort by decreasing value // only need to consider the first x/w items for (auto &[w,items] : by_w) { sort(items.rbegin(),items.rend()); for (int j=0; j<=x; j++) { dp[at][j]=dp[at-1][j]; // implementation: go through as many items at weight w // until we have no space: (copies + 1) * w <= j OR; // until we have no more copies at weight w ll copies=0, type=0, cur=0, totalv=0; while ((copies+1) * w <= j && type < items.size()){ copies++; totalv+=items[type].first; if (dp[at-1][j-copies*w] != INT32_MIN) { // here we need a check to see if it's even possible to make dp[i][j]; dp[at][j]=max(dp[at][j],dp[at-1][j-copies*w]+totalv); } // need to implement the logic of moving on to the next item cur++; if (cur==items[type].second) { type++; cur=0; } } } at++; } cout << *max_element(dp.back().begin(),dp.back().end()) << endl; } int main() { setIO(); solve(); }

knapsack.cpp: In function 'void solve()':
knapsack.cpp:36:61: error: 'INT32_MIN' was not declared in this scope
   36 |     vector<vector<ll>> dp(by_w.size() + 1,vector<ll>(x + 1, INT32_MIN)); // initiliase all values of dp vector as INT32_min
      |                                                             ^~~~~~~~~