Submission #1265181

#TimeUsernameProblemLanguageResultExecution timeMemory
1265181dvdKnapsack (NOI18_knapsack)C++20
100 / 100
38 ms1644 KiB
#include <bits/stdc++.h> using namespace std; struct Item { int v, k; bool operator<(const Item& x) { return v < x.v; } }; const int W = 2e3; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int s, n; cin >> s >> n; vector<vector<Item>> items(W + 1); for (int i = 0; i < n; i++) { int k, v, w; cin >> v >> w >> k; items[w].push_back({v, k}); } vector<int> dp(s + 1, 0); dp[0] = 0; for (int i = 1; i <= s; i++) { sort(items[i].rbegin(), items[i].rend()); int cur = 0, cnt = 0, at = 0; while (cnt * i <= s && at < (int)items[i].size()) { for (int j = s; j >= i; j--) { dp[j] = max(dp[j], dp[j - i] + items[i][at].v); } cur++; cnt++; if (cur >= items[i][at].k) { cur = 0; at++; } } } // for (int i = 0; i <= s; i++) { // cout << dp[i] << " "; // }cout << '\n'; cout << dp[s] << '\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...