Submission #1201379

#TimeUsernameProblemLanguageResultExecution timeMemory
1201379amanthabandKnapsack (NOI18_knapsack)C++20
37 / 100
4 ms6472 KiB
#include <iostream> #include <vector> using namespace std; using ll = long long; ll solve(vector<int> v, vector<int> w, vector<int> k, int S, int n) { vector<int> vv, ww; for (int i = 1; i <= n; ++i) { int value = v[i]; int weight = w[i]; int count = k[i]; for (int b = 1; count > 0; b *= 2) { int take = min(b, count); vv.push_back(value * take); ww.push_back(weight * take); count -= take; } } if (vv.empty()) return 0; int m = vv.size(); vector<vector<ll>> dp(m + 1, vector<ll>(S + 1, 0)); for (int i = 1; i <= m; ++i) { for (int j = 0; j <= S; ++j) { if (j >= ww[i - 1]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - ww[i - 1]] + vv[i - 1]); else dp[i][j] = dp[i - 1][j]; } } return dp[m][S]; } int main() { int S, N; cin >> S >> N; vector<int> v(N + 1), w(N + 1), k(N + 1); for (int i = 1; i <= N; ++i) { cin >> v[i] >> w[i] >> k[i]; } cout << solve(v, w, k, S, N) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...