# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1201897 | durgeshh | Knapsack (NOI18_knapsack) | C++20 | 62 ms | 34376 KiB |
#include <bits/stdc++.h>
#define Task "Task"
#define ll long long
#define vii vector<pair<ll,ll>>
using namespace std;
int n,S,w,v,k;
map<int,vii> by_weight;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(Task".inp","r")) {
freopen(Task".inp","r",stdin);
freopen(Task".out","w",stdout);
}
cin >> S >> n;
for(int i = 0; i < n; i++) {
cin >> v >> w >> k;
if (w <= S && k > 0) by_weight[w].push_back({v,k});
}
vector<vector<ll>> best(by_weight.size() + 1, vector<ll> (S + 1, -1e9));
// best[i][j]: best value u can get by using first i types, and j weights
best[0][0] = 0;
int at = 1;
for(auto &[w, items]: by_weight) {
sort(items.begin(), items.end(),greater<pair<ll,ll>>());
for(int j = 0; j <= S; j++) {
best[at][j] = best[at-1][j];
ll profit = 0;
int type_at = 0;
int copies = 0;
int curr_used = 0;
while((copies + 1) * w <= j && type_at < items.size()) {
++copies;
profit += items[type_at].first;
best[at][j] = max(best[at][j], best[at-1][j - copies * w] + profit);
curr_used++;
if (curr_used == items[type_at].second) {
curr_used = 0;
type_at++;
}
}
}
at++;
}
cout << *max_element(best.back().begin(), best.back().end());
return 0;
}
Compilation message (stderr)
# | 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... |