#include <bits/stdc++.h>
using namespace std;
int main() {
int s, n;
cin >> s >> n;
map<int, vector<array<int, 2>>> mp;
for (int i = 0; i < n; i++) {
int v, w, k;
cin >> v >> w >> k;
mp[w].push_back({v, k});
}
vector<long long> dp(s + 1);
for (auto &[weight, items] : mp) {
sort(items.rbegin(), items.rend());
for (int j = s; j >= 0; j--) {
long long total_price = 0;
int cnt = 0;
for (int x = 0; x < (int)items.size() && (cnt + 1) * weight <= j; x++) {
for (int y = 1; y <= items[x][1] && (cnt + 1) * weight <= j; y++) {
cnt++;
total_price += items[x][0];
dp[j] = max(dp[j], total_price + dp[j - cnt * weight]);
}
}
}
}
cout << dp[s] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |