Submission #1171720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171720		abcsedafaef	Knapsack (NOI18_knapsack)	C++20	100 / 100	130 ms	175684 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long
typedef pair<ll, pair<ll, ll>> item;

void solve() {
    ll x, n;
    cin >> x >> n;
    vector<item> items;
    for (ll i = 0; i < n; i++) {
        ll value, weight, amt;
        cin >> value >> weight >> amt;
        if (weight <= x && amt > 0) {
            items.push_back({value, {weight, amt}});
        }
    }
    sort(items.begin(), items.end(), [](const item &a, const item &b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second.first < b.second.first;
    });
    n = items.size();
    if (n == 0) {
        cout << 0;
        return;
    }
    if (n == 1) {
        ll maxCopies = min(items[0].second.second, x / items[0].second.first);
        cout << maxCopies * items[0].first;
        return;
    }
    vector<item> new_item;
    map<ll, ll> myMap;
    for (item it: items) {
        if (myMap[it.second.first] * it.second.first > x) continue;
        myMap[it.second.first] += it.second.second;
        new_item.push_back(it);
    }
    n = new_item.size();
    vector<vector<ll>> dp(n + 1, vector<ll>(x + 1, 0));
    for (ll i = n - 1; i >= 0; i--) {
        for (ll j = 0; j <= x; j++) {
            ll skip = dp[i + 1][j];
            dp[i][j] = skip;
            for (ll k = 1; k <= new_item[i].second.second && k*new_item[i].second.first<=j ; k++) {
                if (j - k * new_item[i].second.first >= 0) {
                    ll pick = k * new_item[i].first + dp[i + 1][j - k * new_item[i].second.first];
                    dp[i][j] = max(dp[i][j], pick);
                }
            }
        }
    }
    cout << dp[0][x];
}

int main() {
    fast_io;
    solve();
    return 0;
}

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