Submission #1194013

#TimeUsernameProblemLanguageResultExecution timeMemory
1194013dungttKnapsack (NOI18_knapsack)C++20
73 / 100
431 ms327680 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int S, N; cin >> S >> N; // 1) Nhóm theo trọng số vector<vector<int>> byW(S+1); for(int i = 0; i < N; i++){ int V, W, K; cin >> V >> W >> K; // K bản giống hệt, ta push giá trị V, K lần // nhưng thực tế đây chỉ là để minh hoạ: nếu K rất lớn, // bạn có thể cap ngay khi push: int cap = min(K, S / W); while(cap--) byW[W].push_back(V); } // 2) Lọc giữ top ⌊S/w⌋ giá trị cho mỗi w vector<pair<int,int>> items; items.reserve(100000); // ước lượng for(int w = 1; w <= S; w++){ auto &vec = byW[w]; if(vec.empty()) continue; sort(vec.begin(), vec.end(), greater<>()); int take = min((int)vec.size(), S / w); for(int i = 0; i < take; i++){ items.emplace_back(w, vec[i]); } } // 3) Chạy 0/1 Knapsack DP vector<ll> dp(S+1, 0); for(auto [w, v] : items){ for(int j = S; j >= w; j--){ dp[j] = max(dp[j], dp[j-w] + v); } } // 4) Kết quả: max giá trị với trọng số ≤ S ll ans = 0; for(int j = 0; j <= S; j++) ans = max(ans, dp[j]); cout << ans << "\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...