제출 #1086829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086829		selmahbn	Knapsack (NOI18_knapsack)	C++17	100 / 100	88 ms	8084 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define tlll tuple<ll, ll, ll>
#define pll pair<ll, ll>

int main()
{
    ll s, n;
    cin >> s >> n;
    vector<tlll> vs;
    for (ll i = 0; i < n; i++) {
        ll v, w, k;
        cin >> v >> w >> k;
        vs.push_back(make_tuple(w, v, k));
    }
    sort(vs.begin(), vs.end());
    vector<ll> vw;
    vector<vector<pll>> vv;
    ll si = 0;
    for (ll i = 0; i < n; i++) {
        ll w, v, k;
        tie(w, v, k) = vs[i];
        if (i == 0 || w != get<0>(vs[i-1])) {
            vw.push_back(w);
            vv.push_back({});
            si++;
        }
        vv[si-1].push_back(make_pair(v, k));
    }
    vector<ll> ks(s+1, 0);
    for (ll i = 0; i < si; i++) {
        sort(vv[i].rbegin(), vv[i].rend());
        ll most = s/vw[i];
        ll seen = 0;
        ll j = 0;
        while (seen < most && j < (ll) vv[i].size()) {
            for (ll a = s; a >= vw[i]; a--) {
                ks[a] = max(ks[a], ks[a-vw[i]]+vv[i][j].first);
            }
            vv[i][j].second--;
            if (vv[i][j].second == 0) j++;
            seen++;
        }
    }
    ll maxi = 0;
    for (ll v : ks) maxi = max(maxi, v);
    cout << maxi;
    return 0;
}

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