Submission #1191747

#TimeUsernameProblemLanguageResultExecution timeMemory
1191747newsboyKnapsack (NOI18_knapsack)C++20
100 / 100
185 ms249164 KiB
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <map> #include <numeric> #include <iomanip> #include <unordered_set> #include <unordered_map> #include <bitset> #include <queue> #include <deque> #include <stack> #include <cmath> #include <tuple> #include <cassert> #include <list> #include <random> #include <initializer_list> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; constexpr ll inf = 1e18; void solve() { ll s, n; cin >> s >> n; vector<ll> v(n), w(n), k(n); for (ll i = 0; i < n; ++i) { cin >> v[i] >> w[i] >> k[i]; } map<ll, vector<pair<ll, ll>>> by_w; for (ll i = 0; i < n; ++i) { by_w[w[i]].push_back({ v[i], k[i] }); } vector<ll> vv, ww; for (auto e : by_w) { sort(e.second.rbegin(), e.second.rend()); ll tot = s; for (auto c : e.second) { if (tot < e.first) { break; } ll kk = min(c.second, tot / e.first); for (ll i = 0; i < kk; ++i) { ww.push_back(e.first); vv.push_back(c.first); } tot -= ww.back() * kk; } } ll N = ww.size(), W = s; vector<vector<ll>> dp(N + 1, vector<ll> (W + 1)); for (ll j = 0; j <= W; ++j) { dp[0][j] = 0; } for (ll i = 1; i <= N; ++i) { for (ll j = 1; j <= W; ++j) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); } for (ll j = 1; j <= W; ++j) { if (j - ww[i - 1] >= 0) { dp[i][j] = max(dp[i][j], dp[i - 1][j - ww[i - 1]] + vv[i - 1]); } } } ll ans = *max_element(dp[N].begin(), dp[N].end()); cout << ans << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; /*cin >> t;*/ while (t--) { solve(); } 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...