제출 #1194013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194013		dungtt	Knapsack (NOI18_knapsack)	C++20	73 / 100	431 ms	327680 KiB

knapsack

#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;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27