# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
830845 | howard0027 | Knapsack (NOI18_knapsack) | C++14 | 1091 ms | 1300 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.
//knapsack.cpp
#include<cstdio>
#include<vector>
#include<algorithm>
#include<deque>
#include<utility>
int main()
{
int s, n;
std::vector<int> dp;
scanf("%d%d", &s, &n);
dp.resize(s + 1, 0);
for (int i = 0; i < n; ++i)
{
int v, w, k;
scanf("%d%d%d", &v, &w, &k);
for (int r = 0; r < w; ++r)
{
std::deque<std::pair<int, int>> dq;
for (int q = 0; w * q + r <= s; ++q)
{
while (dq.size() && dq.front().second < q - std::min(q, k))
{
dq.pop_front();
}
while (dq.size() && dq.back().first <= dp[w * q + r] - q * v)
{
dq.pop_back();
}
dq.push_back(std::make_pair(dp[w * q + r] - q * v, q));
dp[w * q + r] = dq.front().first + q * v;
//printf("dp[%d][%d] = %d\n", i, w * q + r, dp[w * q + r]);
}
}
}
printf("%d\n", dp[s]);
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... |