# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
675427 | Toxtaq | Knapsack (NOI18_knapsack) | C++17 | 132 ms | 262144 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;
int main()
{
int S, n;
cin >> S >> n;
vector<pair<int, int> >items;
items.push_back({0, 0});
for(int i = 0;i < n;++i){
int v, w, k;
cin >> v >> w >> k;
for(int j = 0;j < k;++j){
items.push_back({w, v});
}
}
n = items.size();
int Max = 0;
vector<vector<int> >dp(n, vector<int>(S + 1, -1e9));
dp[0][0] = 0;
for(int i = 1;i < n;++i){
for(int j = S;j >= 0;--j){
if(j - items[i].first >= 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
Max = max(Max, dp[i][j]);
}
}
cout << Max;
}
# | 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... |