Submission #1163010

#TimeUsernameProblemLanguageResultExecution timeMemory
1163010avighnaKnapsack (NOI18_knapsack)C++20
100 / 100
165 ms246508 KiB
#include <bits/stdc++.h> typedef long long ll; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); ll s, n; std::cin >> s >> n; std::vector<std::vector<std::pair<ll, ll>>> items(2001); for (ll i = 0, v, w, k; i < n; ++i) { std::cin >> v >> w >> k; items[w].push_back({v, k}); } // for the same weight, prefer more valauble items for (auto &i : items) { std::sort(i.rbegin(), i.rend()); } // actual items: O(s log s) many std::vector<std::pair<ll, ll>> a; for (ll w = 1; w <= 2000; ++w) { ll max = 2000 / w; for (auto [v, k] : items[w]) { while (k--) { max--; a.push_back({w, v}); if (max == 0) { break; } } if (max == 0) { break; } } } std::vector<std::vector<ll>> dp(a.size() + 1, std::vector<ll>(s + 1)); for (ll i = a.size(); i >= 0; --i) { for (ll j = s; j >= 0; --j) { if (i == a.size()) { dp[i][j] = 0; continue; } dp[i][j] = dp[i + 1][j]; if (j + a[i].first <= s) { dp[i][j] = std::max(dp[i][j], dp[i + 1][j + a[i].first] + a[i].second); } } } std::cout << dp[0][0] << '\n'; }
#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...