제출 #1367674

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

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int S, N;
    cin >> S >> N;

    vector<vector<int>> bucket(S + 1);

    for (int i = 0; i < N; i++) {
        int v, w, k;
        cin >> v >> w >> k;

        int cnt = min(k, S / w);

        for (int j = 0; j < cnt; j++) {
            bucket[w].push_back(v);
        }
    }

    vector<pair<int,int>> items;

    for (int w = 1; w <= S; w++) {
        auto &vec = bucket[w];

        sort(vec.rbegin(), vec.rend());

        int take = min((int)vec.size(), S / w);

        for (int i = 0; i < take; i++) {
            items.push_back({w, vec[i]});
        }
    }

    vector<int> dp(S + 1);

    for (auto [w, v] : items) {
        for (int j = S; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

    cout << *max_element(dp.begin(), dp.end());

    return 0;
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 17 / 17
• 서브태스크 3: 20 / 20
• 서브태스크 4: 24 / 24
• 서브태스크 5: 0 / 27