Submission #1193714

#TimeUsernameProblemLanguageResultExecution timeMemory
1193714Hamed_GhaffariKnapsack (NOI18_knapsack)C++20
100 / 100
35 ms1608 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define X first #define Y second #define maxs(a, b) (a = max(a,b)) int s, n; vector<pii> sepw[2001]; int dp[2001]; inline void add(int w, int v) { for(int i=s-w; i>=0; i--) maxs(dp[i+w], dp[i]+v); } int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> s >> n; for(int i=0, v, w, k; i<n; i++) { cin >> v >> w >> k; sepw[w].push_back({-v, k}); } for(int w=1; w<=s; w++) { sort(sepw[w].begin(), sepw[w].end()); int cur=0; for(auto i : sepw[w]) for(int j=0; j<i.Y && cur*w<=s; j++) add(w, -i.X), cur++; } cout << dp[s] << '\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...