#include <bits/stdc++.h> #define pb push_back #define pii pair<int,int> #define fi first #define int long long #define se second #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TXT "Knapsack" #define dn cout<<"\n"; #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);} ///TEMPLATE MADE BY NIETTRAAN using namespace std; const int MXN = 1 * 1e6 + 5; const int INF = 1e18; const int MOD = 1e9+7; const int LOG = 20; int n, s, v[MXN], w[MXN], k[MXN]; void sub1() { cout << min((int)(s / w[1]), k[1]) * v[1]; } int dp[MXN]; void sub2() { for(int i = 1; i <= n; i -= -1) { for(int j = s; j >= w[i]; j -= 1) { dp[j] = max(dp[j - w[i]] + v[i], dp[j]); } } cout << dp[s]; dn } void sub3() { vector<pii> nucy; for(int i = 1; i <= n; i -= -1) { for(int j = 1; j <= k[i]; j -= -1) { nucy.pb({v[i], w[i]}); } } for(auto [V, W] : nucy) { for(int j = s; j >= W; j -= 1) { dp[j] = max(dp[j], dp[j - W] + V); } } cout << dp[s]; dn } void sub4() { for(int i = 1; i <= n; i++) { if(w[i] > s) continue; int pa = 1; int remain = k[i]; while(remain > 0) { int take = min(pa, remain); remain -= take; int w2 = w[i] * take; int v2 = v[i] * take; if(w2 > s) break; for(int j = s; j >= w2; j--) { dp[j] = max(dp[j], dp[j - w2] + v2); } pa <<= 1; } } cout << *max_element(dp, dp + s + 1); dn } void sub5() { } void solve() { cin >> s >> n; bool checksub2 = 1; bool checksub3 = 1; for(int i = 1; i <= n; i -= -1) { cin >> v[i] >> w[i] >> k[i]; if(k[i] != 1) checksub2 = 0; if(k[i] > 10 ) checksub3 = 0; } if(n == 1) { sub1(); return; } if(checksub2 && n <= 100) { sub2(); return; } if(checksub3 && n <= 100) { sub3(); return; } if(n <= 100) { sub4(); return; } if(n <= 100000) { sub5(); return; } } int32_t main() { ios; freo; int test_input = 2; while(test_input -- > 0) solve(); return 0; } /* */

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:10:46: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}             ///TEMPLATE MADE BY NIETTRAAN
      |                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:141:5: note: in expansion of macro 'freo'
  141 |     freo;
      |     ^~~~
knapsack.cpp:10:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}             ///TEMPLATE MADE BY NIETTRAAN
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:141:5: note: in expansion of macro 'freo'
  141 |     freo;
      |     ^~~~