Submission #1171966

#TimeUsernameProblemLanguageResultExecution timeMemory
1171966jrkeKnapsack (NOI18_knapsack)C++20
100 / 100
81 ms2884 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define ll long long int main() { ll n, s; cin >> s >> n; vector<vector<pair<ll, ll>>> dp(s + 1); for (int i = 0; i < n; i++) { ll v, w, k; cin >> v >> w >> k; dp[w].push_back({v, min(k, s / w)}); } vector<ll> mx(s + 1, 0); ll ans = 0; for (int i = 1; i < s + 1; i++) { sort(dp[i].begin(), dp[i].end()); ll cnt = 0; ll idx = dp[i].size(); while (cnt < s / i && idx) { idx--; for (int j = 0; j < dp[i][idx].second; j++) { cnt++; for (int k = s; k >= i; k--) { mx[k] = max(mx[k], mx[k - i] + dp[i][idx].first); ans = max(ans, mx[k]); } if (cnt == s / i) break; } } } cout << ans << endl; }
#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...