Submission #1188011

#TimeUsernameProblemLanguageResultExecution timeMemory
1188011mehmetkaganKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms328 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; k = min(k, S / w); 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...