Submission #1186951

#TimeUsernameProblemLanguageResultExecution timeMemory
1186951mehmetkaganKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms16800 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int S, N; cin >> S >> N; vector<pair<int, int>> items; for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; for (int j = 1; k > 0; j <<= 1) { int take = min(k, j); items.push_back({v * take, w * take}); k -= take; } } vector<int> dp(S + 1, 0); for (auto [v, w] : items) { for (int j = S; j >= w; j--) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << *max_element(dp.begin(), dp.end()) << '\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...