Submission #772112

#TimeUsernameProblemLanguageResultExecution timeMemory
772112asdf334Knapsack (NOI18_knapsack)C++17
73 / 100
1090 ms340 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll dp[2001]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); for (ll& i : dp) i = -1; dp[0] = 0; ll S, N; cin >> S >> N; ll ans = 0; for (int i = 0; i < N; ++i) { ll v, w, k; cin >> v >> w >> k; for (ll i = 2000; i >= 0; --i) { if (dp[i] >= 0) { for (ll c = 1; c <= min((ll)floor((S - i) / w), k); ++c) { dp[c * w + i] = max(dp[c * w + i], dp[i] + c * v); ans = max(ans, dp[c * w + i]); } } } } cout << ans << '\n'; }
#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...