Submission #1212179

#TimeUsernameProblemLanguageResultExecution timeMemory
1212179nanh0607Knapsack (NOI18_knapsack)C++17
49 / 100
116 ms444 KiB
#include <bits/stdc++.h> #define FOR(i, l, r) for (int i=l; i<=r; i++) #define FOR2(i, l, r) for (int i=l; i>=r; i--) #define ALL(v) v.begin(), v.end() #define fi first #define se second #define pii pair<int, int> #define pb push_back using namespace std; void solve() { int s, n; cin >> s >> n; map<int, vector<pii>> groups; FOR(i, 1, n) { int v, w, k; cin >> v >> w >> k; groups[w].pb({v, k}); } // for (auto i:groups) { // cout << i.fi; ce; // for (auto j:i.se) { // cout << j.fi << ' ' << j.se; ce; // } // ce; // } vector<int> dp(s+1, 0); for (auto& group:groups) { int w = group.fi; int k = (int)s/w; sort(ALL(group.se), [](const pii &a, const pii &b) { return a.first > b.first; }); for (auto item:group.se) { int v = item.fi, m = item.se; while (k-- && m--) { FOR2(i, s, w) { dp[i] = max(dp[i], dp[i-w] + v); } } if (k == 0) {break;} } } cout << dp[s]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); }
#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...