Submission #1214779

#TimeUsernameProblemLanguageResultExecution timeMemory
1214779WoahManKnapsack (NOI18_knapsack)C++20
100 / 100
71 ms34376 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define mod 998244353 template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << '{' << p.first << ", " << p.second << '}'; } template <class T, class = decay_t<decltype(*begin(declval<T>()))>, class = enable_if_t<!is_same<T, string>::value>> ostream &operator<<(ostream &os, const T &c) { os << '['; for (auto it = c.begin(); it != c.end(); ++it) os << &", "[2 * (it == c.begin())] << *it; return os << ']'; } // Support up to 5 args #define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N #define _FE_0(_CALL, ...) #define _FE_1(_CALL, x) _CALL(x) #define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__) #define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__) #define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__) #define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__) #define FOR_EACH_MACRO(MACRO, ...) \ _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0) \ (MACRO, ##__VA_ARGS__) // Change output format here #define out(x) #x " = " << x << "; " #define dbg(...) \ cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n" int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int w_tot, n; cin >> w_tot >> n; map<int, vector<pair<int, int>>> mp_w; for (int i = 0; i < n; i++) { int v, w, cnt; cin >> v >> w >> cnt; if (w <= w_tot && cnt > 0) { mp_w[w].push_back({v, cnt}); } } vector<vector<int>> dp(mp_w.size() + 1, vector<int>(w_tot + 1, 0)); int idx = 1; dp[0][0] = 0; for (auto &[w, items] : mp_w) { sort(items.begin(), items.end(), greater<pair<int, int>>()); for (int i = 0; i <= w_tot; i++) { dp[idx][i] = dp[idx - 1][i]; // Not taking any item of this weight int copies = 0; int type_at = 0; int curr_used = 0; int profit = 0; while ((copies + 1) * w <= i && type_at < items.size()) { copies++; profit += items[type_at].first; if (dp[idx - 1][i - copies * w] != INT32_MIN) { dp[idx][i] = std::max(dp[idx][i], dp[idx - 1][i - copies * w] + profit); } curr_used++; if (curr_used == items[type_at].second) { curr_used = 0; type_at++; } } } idx++; } int max_value = 0; for (int i = 0; i <= w_tot; i++) { max_value = max(max_value, dp[mp_w.size()][i]); } cout << max_value << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...