#include <bits/stdc++.h>
using namespace std;
const int M = 100004;
const int N = 2004;
vector<pair<int, int>> p;
long long s, n, w, v, k, dp[N];
int main() {
cin >> s >> n;
if (n == 1) {
cin >> v >> w >> k;
cout << v * min(k, s / w) << endl;
} else {
for (int i = 0; i < n; i++) {
cin >> v >> w >> k;
while (k--) {
p.push_back({v, w});
}
}
for (auto [v, w] : p) {
for (int j = s; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
long long ans = 0;
for (int i = 1; i <= s; i++) {
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
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... |