| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 528456 | theysoldtheworld | Knapsack (NOI18_knapsack) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Item {
long long v , w , k;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int S , N;
cin >> S >> N;
vector<Item> a(N);
for (int i = 0 ; i < N ; i++) {
cin >> a[i].v >> a[i].w >> a[i].k;
a[i].k = min(a[i].k , S);
}
auto Get_candidates = [&](long long val) {
vector<long long> c;
int po = -1;
for (int i = 30 ; i >= 0 ; i--) {
long long cur = (1LL << i);
if (cur & val) {
if (po == -1) {
po = (1 << i) - 1;
c.push_back(1);
}
else {
c.push_back(cur);
}
}
}
for (int i = 30 ; i >= 0 ; i--) {
long long cur = (1LL << i);
if (po & cur) {
c.push_back(cur);
}
}
return c;
};
vector<pair<long long , long long>> who;
for (int i = 0 ; i < N ; i++) {
vector<long long> c = Get_candidates(a[i].k);
for (int j = 0 ; j < (int)c.size() ; j++) {
long long cost = a[i].w * c[j];
long long add = a[i].v * c[j];
who.emplace_back(add , cost);
}
}
vector<long long> dp(S + 1);
vector<bool> Reachable(S + 1);
Reachable[0] = true;
for (int i = 0 ; i < (int)who.size() ; i++) {
for (int j = S ; j >= 0 ; j--) {
if (j + who[i].second <= S && Reachable[j]) {
Reachable[who[i].second + j] = true;
dp[who[i].second + j] = max(dp[who[i].second + j] , dp[j] + who[i].first);
}
}
}
cout << *max_element(dp.begin(),dp.end()) << '\n';
return 0;
}