#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<long long>
#define pb push_back
#define endll "\n"
#define vvll vector<vector<long long>>
const int MOD = 1e9 + 7;
#define rep(i, a , n) for (int i = a; i < (n); i++)
#define nrep(i, n , a) for (int i = n-1; i >= (a); i--)
void solve()
{
ll s, n; cin >> s >> n;
vector<pair<ll, ll>> items;
rep (i, 0, n) {
ll value, weight, count;
cin >> value >> weight >> count;
ll j(1);
while (j<= count){
ll curr_val = value * j;
ll curr_weight = weight * j;
if (curr_weight > s) break;
items.pb({curr_val, curr_weight});
count -= j;
j *= 2;
}
if (count > 0) {
ll curr_val = value * count;
ll curr_weight = weight * count;
if (curr_weight <= s) {
items.pb({curr_val, curr_weight});
}
}
}
vll dp(s+1, 0);
for (auto item: items) {
ll value = item.first, weight = item.second;
nrep (i, s+1, weight){
dp[i] = max(dp[i], dp[i - weight] + value);
}
}
cout << dp[s] << endll;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
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... |