Submission #1131652

#TimeUsernameProblemLanguageResultExecution timeMemory
1131652khoi13209Knapsack (NOI18_knapsack)C++20
0 / 100
0 ms324 KiB
/** * author: daotuankhoi * created: 29.09.2024 20:25:04 **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif int64_t dp[200005]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int64_t> we(1), va(1); for (int i = 1; i <= n; i++) { int64_t w, v, a; cin >> w >> v >> a; int64_t bit = 1; while (bit <= a) { we.emplace_back(w * bit); va.emplace_back(v * bit); a -= bit; bit <<= 1; } if (a > 0) { we.emplace_back(w * a); va.emplace_back(v * a); } } for (int i = 1; i < we.size(); i++) { for (int j = m; j >= we[i]; j--) { dp[j] = max(dp[j], dp[j - we[i]] + va[i]); } } cout << dp[m]; 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...