#include <algorithm> #include <cstdio> #include <functional> #include <utility> #include <vector> #define int long long #define MAXN 100001 using namespace std; int V[MAXN], W[MAXN], K[MAXN]; vector<pair<int, int> > vals[2001]; // {value, cnt} int dp[2001][2001]; signed main () { freopen ("test.in", "r", stdin); int S, N; scanf ("%lld%lld", &S, &N); for (int i = 1; i <= N; ++i) { scanf ("%lld%lld%lld", &V[i], &W[i], &K[i]); vals[W[i]].push_back ({ V[i], K[i] }); } vector<int> widx = { 0 }; for (int i = 1; i <= 2000; ++i) { if (vals[i].size () > 0) widx.push_back (i); } for (int i = 1; i < widx.size (); ++i) { auto &v = vals[widx[i]]; sort (v.begin (), v.end (), greater<> ()); for (int j = 1; j <= S; ++j) { dp[i][j] = dp[i - 1][j]; int vsum = 0; int vij = 0; int vi = 0; for (int k = 1; vi < v.size () && j >= k * widx[i]; ++k) { vsum += v[vi].first; if (vij == v[vi].second - 1) { ++vi; vij = 0; } else { ++vij; } dp[i][j] = max (dp[i][j], dp[i - 1][j - k * widx[i]] + vsum); } // printf ("%2lld ", dp[i][j]); } // putchar ('\n'); } printf ("%lld\n", dp[widx.size () - 1][S]); return 0; }

knapsack.cpp: In function 'int main()':
knapsack.cpp:20:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen ("test.in", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:23:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf ("%lld%lld", &S, &N);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:26:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf ("%lld%lld%lld", &V[i], &W[i], &K[i]);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~