Submission #1223322

#TimeUsernameProblemLanguageResultExecution timeMemory
1223322eduardmmKnapsack (NOI18_knapsack)C++20
100 / 100
57 ms6216 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ cin.tie(0)->sync_with_stdio(0); int n, s; cin >> s >> n; vector<vector<ll>> a(n, vector<ll> (3)); for (int i = 0; i < n; ++i){ cin >> a[i][0] >> a[i][1] >> a[i][2]; } sort(a.begin(), a.end()); reverse(a.begin(), a.end()); vector<ll> v, w; vector<int> count(s + 1); for (int i = 0; i < n; ++i){ if (count[a[i][1]] < s/a[i][1]){ while (count[a[i][1]] < s/a[i][1] && a[i][2] > 0){ v.push_back(a[i][0]); w.push_back(a[i][1]); a[i][2]--; count[a[i][1]]++; } } } vector<ll> dp(s + 1, -1); dp[0] = 0; for (int i = 0; i < v.size(); ++i){ for (int j = s; j >= 0; --j){ if (j - w[i] >= 0 && dp[j - w[i]] != -1){ dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } } ll ans = 0; for (int i = 0; i <= s; ++i) ans = max(dp[i], ans); cout << ans << '\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...