제출 #1192990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192990		PakinDioxide	Knapsack (NOI18_knapsack)	C++17	100 / 100	49 ms	3268 KiB

knapsack

/*
    author  : PakinDioxide
    created : 20/04/2025 09:23
    task    : NOI18_knapsack
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int s, n;
    cin >> s >> n;
    vector <pair <ll, ll>> V[s+1], A;
    for (int i = 0; i < n; i++) {
        ll v, w, c;
        cin >> v >> w >> c;
        V[w].emplace_back(v, c);
    }
    for (int i = 0; i <= s; i++) {
        sort(V[i].begin(), V[i].end());
        reverse(V[i].begin(), V[i].end());
        int cnt = 0;
        for (auto &[x, y] : V[i]) while (y > 0 && cnt*i <= s) A.emplace_back(x, i), cnt++, y--;
    }
    vector <ll> dp(s+1, LLONG_MIN);
    dp[0] = 0;
    ll ans = 0;
    for (auto &[v, w] : A) for (int i = s; i >= w; i--) dp[i] = max(dp[i], dp[i-w] + v), ans = max(ans, dp[i]);
    cout << ans << '\n';
}

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