Submission #1231730

#TimeUsernameProblemLanguageResultExecution timeMemory
1231730mathmemonistKnapsack (NOI18_knapsack)C++20
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; const int MAXS = 2005; int dp[MAXS]; int main() { ios::sync_with_stdio(false); cin.tie(0); int S, N; cin >> S >> N; vector<pair<int, int>> items; // (value, weight) for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; // Binary decomposition of count k for (int j = 1; k > 0; j <<= 1) { int take = min(j, k); items.emplace_back(v * take, w * take); k -= take; } } // Classic 0/1 Knapsack with expanded items for (auto [val, wt] : items) { for (int s = S; s >= wt; s--) { dp[s] = max(dp[s], dp[s - wt] + val); } } 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...