| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1225058 | bounce_29 | Knapsack (NOI18_knapsack) | C++20 | 0 ms | 0 KiB |
#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<vector<pair<ll, ll>>> items(s+1);
rep (i, 0, n) {
ll value, weight, count;
cin >> value >> weight >> count;
if (weight > s) continue;
items[weight].push_back({value, count});
}
vector<pair<ll, ll>> all_items;
rep (i, 1, s+1){
sort(items[i].begin(), items[i].end(), greater<pair<ll, ll>>());
ll accu_weight = 0;
for (auto item: items[i]) {
ll y = 1
ll value = item.first, count = item.second;
while(1){
accu_weight += i * y;
if (accu_weight > s) break;
if (count == 0) break;
if (y > count) y = count;
all_items.pb({y*value, i * y});
count -= y;
y*=2;
}
if (accu_weight > s) break;
}
}
vector<ll> dp(s+1, 0);
for (auto item: all_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;
}