Submission #1221099

#TimeUsernameProblemLanguageResultExecution timeMemory
1221099longggggKnapsack (NOI18_knapsack)C++17
73 / 100
1097 ms9524 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int main() { ios::sync_with_stdio(0); cin.tie(0); int s, n; cin >> s >> n; vector<vector<pair<int, int>>> weight(2001); for (int i = 0; i < n; ++i) { int v, w, k; cin >> v >> w >> k; if (w <= s) weight[w].emplace_back(v, k); } vector<ll> dp(s + 1, 0); for (int w = 1; w <= 2000; ++w) { if (weight[w].empty()) continue; vector<pair<int, int>> items; // Gom lại tất cả các vật có cùng trọng lượng w for (auto [v, k] : weight[w]) { int max_take = min(k, s / w); // Giới hạn số món cần sinh for (ll pw = 1; max_take > 0; pw <<= 1) { int use = min((ll)max_take, pw); items.emplace_back(w * use, v * use); max_take -= use; } } // Knapsack 0/1 cho toàn bộ món cùng trọng lượng w for (auto [ww, vv] : items) { for (int j = s; j >= ww; --j) { dp[j] = max(dp[j], dp[j - ww] + vv); } } } cout << *max_element(dp.begin(), dp.end()) << '\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...