제출 #1254494

#제출 시각아이디문제언어결과실행 시간메모리
1254494shakilinnovateKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms416 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll S, N; cin >> S >> N; vector<ll> dp(S + 1, 0); // Start with 0, no items taken for (int i = 0; i < N; i++) { ll v, w, k; cin >> v >> w >> k; // ✅ Treat as unbounded knapsack if weight × k exceeds capacity if (w * k >= S) { for (ll j = w; j <= S; j++) { dp[j] = max(dp[j], dp[j - w] + v); } } else { // Binary optimization for bounded knapsack for (ll cnt = 1; k > 0; cnt <<= 1) { ll take = min(cnt, k); k -= take; ll totalValue = v * take; ll totalWeight = w * take; for (ll j = S; j >= totalWeight; j--) { dp[j] = max(dp[j], dp[j - totalWeight] + totalValue); } } } } cout << *max_element(dp.begin(), dp.end()) << 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...