Submission #1211913

#TimeUsernameProblemLanguageResultExecution timeMemory
1211913nanh0607Knapsack (NOI18_knapsack)C++17
17 / 100
1 ms528 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 fi first #define se second #define pb push_back #define pii pair<int, int> #define ce cout << endl 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; for (auto item:group.se) { int v = item.fi, k = item.se; int cur_wei = 0, cnt = 0; while (k-- && cur_wei < s) { cnt += 1; cur_wei += w; FOR2(i, s, cur_wei) { dp[i] = max(dp[i], dp[i-cur_wei] + cnt*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...