Submission #772113

#TimeUsernameProblemLanguageResultExecution timeMemory
772113asdf334Knapsack (NOI18_knapsack)C++17
73 / 100
1078 ms340 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; ll dp[2001]; bool vis[2001]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); vis[0] = true; 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 (vis[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]); vis[c * w + i] = true; } } } } cout << ans << '\n'; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:15: warning: comparison of constant '0' with boolean expression is always true [-Wbool-compare]
   14 |    if (vis[i] >= 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...