# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1053976 | ssitaram | Knapsack (NOI18_knapsack) | C++17 | 1065 ms | 4188 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;
typedef long long ll;
struct item {
ll v, w, k;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
ll s, n; cin >> s >> n;
vector<item> v(n);
for (ll i = 0; i < n; ++i) {
cin >> v[i].v >> v[i].w >> v[i].k;
}
vector<ll> best(s + 1);
for (ll i = 0; i < n; ++i) {
vector<set<pair<ll, ll>>> prevs(v[i].w);
vector<ll> valof(s + 1);
vector<ll> prbest = best;
ll last = 3001;
for (ll j = 0; j <= s; ++j) {
if (!(j % v[i].w)) --last;
valof[j] = best[j] + v[i].v * last;
prevs[j % v[i].w].insert({valof[j], j});
if (prevs[j % v[i].w].size() == v[i].k + 2) {
ll idx = j - v[i].w * (v[i].k + 1);
prevs[j % v[i].w].erase({valof[idx], idx});
}
ll bestidx = (*prev(prevs[j % v[i].w].end())).second;
best[j] = prbest[bestidx] + (j - bestidx) / v[i].w * v[i].v;
}
}
cout << best.back() << '\n';
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... |