#include<bits/stdc++.h> using namespace std; #define NAME "TEST" #define nl '\n' #define allofa(x,sz) x+1,x+sz+1 #define allof(x) x.begin(),x.end() #define mset(x,val) memset(x,val,sizeof(x)) template<typename T> T Max(T x, T y){return(x>y)?x:y;}; template<typename T> T Min(T x, T y){return(x<y)?x:y;}; 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;}; typedef long long ll; const ll mod = (long long)1e9+7; const ll LINF = (long long)1e18; const int INF = (int)1e9; const int MAXN = (int)1e5+5; int v[MAXN],w[MAXN],k[MAXN]; ll dp[2010]; int s,n; void ccps() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if(fopen(NAME".inp","r")) { freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout); } } namespace sub2 { bool check() { for (int i = 1; i<=n; i++) { if(k[i]!=1) return false; } return n<=100; } void sol() { fill(allofa(dp,s),0); for (int i = 1; i<=n; i++) { for (int c = s; c>=w[i]; c--) { maximize(dp[c],dp[c-w[i]]+v[i]); } } cout << dp[s]; } } namespace sub3 { bool check() { for (int i = 1; i<=n; i++) { if(k[i]>10) return false; } return n<=100; } void sol() { for (int i = 1; i<=n; i++) { for (int c = s; c>=w[i]; c--) { for (int t = 1; t<=k[i]; t++) { if(c>=t*w[i]) maximize(dp[c],dp[c-t*w[i]]+1LL*t*v[i]); } } } cout << dp[s]; } } namespace sub4 { bool check() { return n<=100; } void sol() { for (int i = 1; i<=n; i++) { int cnt = k[i]; int base = 1; while(cnt) { int t = Min<int>(base,cnt); for (int c = s; c>=w[i]; c--) { if(c>=t*w[i]) maximize(dp[c],dp[c-t*w[i]]+1LL*t*v[i]); } cnt-=t; base<<=1; } } cout << dp[s]; } } signed main() { ccps(); cin >> s >> n; for (int i = 1; i<=n; i++) { cin >> v[i] >> w[i] >> k[i]; } if(sub2::check()) return sub2::sol(),0; else if(sub3::check()) return sub3::sol(),0; else if(sub4::check()) return sub4::sol(),0; }

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