#include <bits/stdc++.h> #define el '\n' #define FNAME "Knapsack" #define allof(x) x.begin(),x.end() #define allof1(x) x.begin()+1,x.end() #define mset(x,n) memset(x,(n),sizeof(x)) using namespace std; const long long MOD = (long long) 1e9 + 7; template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;} template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;} void setup(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if (fopen(FNAME".inp","r")){ freopen(FNAME".inp","r",stdin); freopen(FNAME".out","w",stdout); } } const long long INF = (long long) 1e16 + 15092007; struct Goods{ long long val,weight,quantity; Goods(long long v,long long w,long long q):val(v),weight(w),quantity(q) {} bool operator < (const Goods &other) const{ if (val != other.val) return val > other.val; if (quantity != other.quantity) return quantity > other.quantity; return weight > other.weight; } }; int numGoods,maxWeight; vector<Goods> goods; void init(){ cin>>maxWeight>>numGoods; for (int i = 0; i < numGoods; i++){ long long v,w,q; cin>>v>>w>>q; goods.emplace_back(v,w,q); } } void sol(){ vector<long long> dp(maxWeight + 1, 0); vector<vector<Goods>> goodsByW(maxWeight + 1); vector<int> ws; for (const Goods &g : goods){ goodsByW[g.weight].emplace_back(g); ws.push_back(g.weight); } sort(allof(ws)); ws.resize(unique(allof(ws)) - ws.begin()); for (int w : ws){ vector<Goods> &curGoods = goodsByW[w]; sort(allof(curGoods)); int totalTake = 0, cnt = 0, ptr = 0; while (totalTake * w <= maxWeight and ptr < (int)curGoods.size()){ for (int j = maxWeight; j >= w; j--){ maximize(dp[j], dp[j - w] + curGoods[ptr].val); } cnt++; totalTake++; if (cnt >= curGoods[ptr].quantity){ cnt = 0; ptr++; } } } cout<<dp.back(); } int main(){ setup(); init(); sol(); }

knapsack.cpp: In function 'void setup()':
knapsack.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen(FNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(FNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~