Submission #1188306

#TimeUsernameProblemLanguageResultExecution timeMemory
1188306alwaus424Knapsack (NOI18_knapsack)C++20
17 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; vector<pair<int, int>> items; // (value, weight) for (int i = 0; i < N; i++) { int v, w, k; cin >> v >> w >> k; // Binary splitting for (int j = 1; j <= k; j <<= 1) { if (k == 0) break; int cnt = min(j, k); items.push_back({cnt * v, cnt * w}); k -= cnt; } } vector<ll> dp(S + 1, 0); // dp[i] = max value with i weight for (auto [val, wt] : items) { for (int i = S; i >= wt; i--) { dp[i] = max(dp[i], dp[i - wt] + val); } } cout << *max_element(dp.begin(), dp.end()) << "\n"; 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...