Submission #1193249

#TimeUsernameProblemLanguageResultExecution timeMemory
1193249dprtoKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms3776 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 1e5 + 5; int s, n, dp[MAXN]; vector<pair<int, int>> wei[MAXN]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s >> n; for(int i = 1; i <= n; ++i){ int v, w, k; cin >> v >> w >> k; if(w > s) continue; wei[w].push_back({v, k}); } for(int i = 1; i <= s; ++i){ dp[i] = -1e9; } dp[0] = 0; for(int w = 1; w <= s; ++w){ sort(wei[w].begin(), wei[w].end(), greater<>()); } for(int w = 1; w <= s; ++w){ if(wei[w].empty()) continue; vector<int> items; for(auto [val, cnt] : wei[w]){ for(int i = s; i >= 0; --i){ if(dp[i] == -1e9) continue; for(int k = 1; k <= cnt and i + w * k <= s; ++k){ dp[i + w * k] = max(dp[i + w * k], dp[i] + val * k); } } } } int res = 0; for(int i = 1; i <= s; ++i){ res = max(res, dp[i]); } cout << res; 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...