Submission #1140189

#TimeUsernameProblemLanguageResultExecution timeMemory
1140189hemaprakashKnapsack (NOI18_knapsack)C++20
100 / 100
86 ms1864 KiB
#include <bits/stdc++.h> using namespace std; int main() { int s, n; cin >> s >> n; map<int, vector<array<int, 2>>> mp; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; mp[w].push_back({v, k}); } vector<long long> dp(s + 1); for (auto &[weight, items] : mp) { sort(items.rbegin(), items.rend()); for (int j = s; j >= 0; j--) { long long total_price = 0; int cnt = 0; for (int x = 0; x < (int)items.size() && (cnt + 1) * weight <= j; x++) { for (int y = 1; y <= items[x][1] && (cnt + 1) * weight <= j; y++) { cnt++; total_price += items[x][0]; dp[j] = max(dp[j], total_price + dp[j - cnt * weight]); } } } } cout << dp[s] << "\n"; 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...