Submission #1202848

#TimeUsernameProblemLanguageResultExecution timeMemory
1202848amanthabandKnapsack (NOI18_knapsack)C++20
73 / 100
198 ms327680 KiB
#include <bits/stdc++.h> #include <iostream> #include <vector> using namespace std; using ll = long long; ll solve(vector<ll> v, vector<ll> w, ll S, ll n) { ll dp[n + 1][S + 1]; for (int i = 0; i <= S; i++) { dp[0][i] = 0; } for (int i = 0; i <= n; i++) { dp[i][0] = 0; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= S; j++) { if (j - w[i] >= 0) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][S]; } int main() { ll S, N; cin >> S >> N; vector<ll> v(1), w(1), k(N); for (int i = 0; i < N; ++i) { ll val, wei, cnt; cin >> val >> wei >> cnt; k[i] = cnt; for (ll j = 1; cnt > 0; j <<= 1) { ll take = min(j, cnt); v.push_back(val * take); w.push_back(wei * take); cnt -= take; } } ll newN = v.size() - 1; ll ans = solve(v, w, S, newN); cout << ans << endl; return 0; }
#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...