Submission #1043810

#TimeUsernameProblemLanguageResultExecution timeMemory
1043810vaneaKnapsack (NOI18_knapsack)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 2e3+10; ll dp[mxN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll s, n; cin >> s >> n; for(int i = 0; i < n; i++) { ll v, w, k; cin >> v >> w >> k; vector<ll> cnt(s+5); for(int j = 0; j <= s-w; j++) { if(dp[j] > dp[j+w]) { dp[j+w] = dp[j]; cnt[j+w] = cnt[j]; } if(dp[j]+v > dp[j+w] && cnt[j]+1 <= k) { cnt[j+w] = cnt[j]+1; dp[j+w] = dp[j]+v; } } for(int j = 0; j <= s; j++) { cout << dp[j] << ' '; } cout << '\n'; } ll ans = 0; for(int i = 0; i <= s; i++) { ans = max(ans, dp[i]); } cout << ans; 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...