Submission #1236414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236414		jiraphatnam2204	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	5644 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Item pair<ll, ll>
#define ItemList vector<Item>

const ll mod=998244353;
const ll MAX_CAP=2007;
const ll MAX_ITEMS=1e5+7;

ll values[MAX_ITEMS], weights[MAX_ITEMS], quantities[MAX_ITEMS];

void solve(){
    ll S, N; cin>>S>>N;
    ll max_quantity=0;
    for (int i=0; i<N; i++) {
        cin >> values[i] >> weights[i] >> quantities[i];
        max_quantity = max(max_quantity, quantities[i]);
    }
    if (N==1) {
        ll items_to_take = 0;
        if (weights[0] > 0) {
            items_to_take = std::min(S / weights[0], quantities[0]);
        }
        cout << values[0] * items_to_take << '\n';
    } else if (N <= 100 && max_quantity <= 10) {
        ll dp[MAX_CAP];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < N; i++) {
            for (ll capacity = S; capacity >= weights[i]; capacity--) {
                for (int count = 1; count <= quantities[i]; count++) {
                    if (capacity >= weights[i] * count) {
                        dp[capacity] = max(dp[capacity], dp[capacity - weights[i] * count] + values[i] * count);
                    }
                }
            }
        }
        cout << dp[S] << '\n';
    } else {
        ll dp[MAX_CAP];
        memset(dp, 0, sizeof(dp));

        ItemList items_by_weight[MAX_CAP];
        for (int i = 0; i < N; i++) {
            if (weights[i] < MAX_CAP) {
                items_by_weight[weights[i]].push_back({values[i], quantities[i]});
            }
        }

        for (int w = 1; w < MAX_CAP; w++) {
            if (items_by_weight[w].empty()) continue;

            sort(items_by_weight[w].rbegin(), items_by_weight[w].rend());

            int current_item_idx = 0;
            for (int i = 0; i < S / w; ++i) {
                if (current_item_idx >= items_by_weight[w].size()) break;

                ll current_value = items_by_weight[w][current_item_idx].first;

                for (ll capacity = S; capacity >= w; capacity--) {
                    dp[capacity] = std::max(dp[capacity], dp[capacity - w] + current_value);
                }

                // "Use up" one item of this type and move to the next if needed.
                items_by_weight[w][current_item_idx].second--;
                if (items_by_weight[w][current_item_idx].second == 0) {
                    current_item_idx++;
                }
            }
        }
        std::cout << dp[S] << std::endl;
    }
    return;
}

int main(){
	cin.tie(NULL)->sync_with_stdio(false);
	// precomputation
	//
	const bool multitest=false;
	if(multitest){
		ll t; cin>>t;
		while(t--){
			solve();
		}
	} else {
		solve();
	}
	return 0;
}

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