Submission #1254821

#TimeUsernameProblemLanguageResultExecution timeMemory
1254821orny_nabilaKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms16796 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int32_t main() { int S, N; cin >> S >> N; vector<pair<int, int>> final_items; for(int i = 0; i < N; ++i) { int val, wt, k; cin >> val >> wt >> k; for(int b = 1; k > 0; b <<= 1) { int cnt = min(b, k); k -= cnt; final_items.push_back({wt * cnt, val * cnt}); } } vector<int> dp(S + 1, 0); for(auto& [w, v] : final_items) { for(int j = S; j >= w; --j) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[S]; 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...