# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1043810 | vanea | Knapsack (NOI18_knapsack) | C++14 | 1 ms | 348 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;
using ll = long long;
const int mxN = 2e3+10;
ll dp[mxN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll s, n;
cin >> s >> n;
for(int i = 0; i < n; i++) {
ll v, w, k;
cin >> v >> w >> k;
vector<ll> cnt(s+5);
for(int j = 0; j <= s-w; j++) {
if(dp[j] > dp[j+w]) {
dp[j+w] = dp[j];
cnt[j+w] = cnt[j];
}
if(dp[j]+v > dp[j+w] && cnt[j]+1 <= k) {
cnt[j+w] = cnt[j]+1;
dp[j+w] = dp[j]+v;
}
}
for(int j = 0; j <= s; j++) {
cout << dp[j] << ' ';
# | 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... |