Submission #1186955

#TimeUsernameProblemLanguageResultExecution timeMemory
1186955mehmetkaganKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms440 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<int> dp(S + 1, 0); for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; if (k * w >= S) { // Unbounded knapsack for (int j = w; j <= S; j++) { dp[j] = max(dp[j], dp[j - w] + v); } } else { // Binary grouping for (int t = 1; k > 0; t <<= 1) { int take = min(t, k); int val = v * take; int wei = w * take; for (int j = S; j >= wei; j--) { dp[j] = max(dp[j], dp[j - wei] + val); } k -= take; } } } 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...