Submission #1236422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236422		jiraphatnam2204	Knapsack (NOI18_knapsack)	C++20	100 / 100	35 ms	5192 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]);
    }
    ll dp[MAX_CAP];
    memset(dp, 0, sizeof(dp));

    ItemList items_by_weight[MAX_CAP];
    for (ll i=0; i<N; i++){
        items_by_weight[weights[i]].push_back({values[i], quantities[i]});
    }
    for (ll w=1; w<MAX_CAP; w++){
        if(items_by_weight[w].empty()) continue;
        sort(items_by_weight[w].rbegin(), items_by_weight[w].rend());
        ll current_item_idx = 0;

        for (ll 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]=max(dp[capacity], dp[capacity-w]+current_value);
            }
            items_by_weight[w][current_item_idx].second--;
            if (items_by_weight[w][current_item_idx].second==0) {
                current_item_idx++;
            }
        }
    }
    cout << dp[S] << '\n';
    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