제출 #1257302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257302		luvletturr	Knapsack (NOI18_knapsack)	C++20	100 / 100	179 ms	245192 KiB

knapsack

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

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

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

        vector<vector<array<int, 2>>> items(S + 1);
        for (int i = 1; i <= N; ++i) {
                int v, w, k; cin >> v >> w >> k;

                items[w].push_back({v, k});
        }

        
        vector<array<int, 2>> newitems = {{0, 0}};
        for (int i = 1; i <= S; ++i) {
                sort(items[i].begin(), items[i].end(), [&](const array<int, 2> a, const array<int, 2> b) {
                        return a[0] > b[0];
                });
                int cur = 0;
                for (auto x : items[i]) {
                        int p = min((S / i) - cur, x[1]);

                        for (int j = 1; j <= p; ++j) {
                                newitems.push_back({x[0], i});
                        }
                        cur += p;
                        if (cur == (S / i)) break;
                }
        }

        int NN = newitems.size() - 1;
        vector<vector<int64_t>> DP(NN + 1, vector<int64_t>(S + 1));
        for (int i = 1; i <= NN; ++i) {
                for (int j = 1; j <= S; ++j) {
                        if (j >= newitems[i][1]) {
                                DP[i][j] += max(DP[i][j], DP[i - 1][j - newitems[i][1]] + newitems[i][0]);
                                
                        }

                        DP[i][j] = max(DP[i][j], DP[i - 1][j]);
                }
        }
        
        cout << DP[NN][S] << '\n';

        return 0;
}

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