Submission #1236359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236359		jiraphatnam2204	Knapsack (NOI18_knapsack)	C++20	73 / 100	1097 ms	16796 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const ll mod=998244353;

struct Item{
    ll v;
    ll w;
};

ll dp[2002];

void solve(){
    ll s, n; cin>>s>>n;
    vector<Item> items;
    for (ll i=0; i<n; i++){
        ll v, w, k;
        cin>>v>>w>>k;
        for (ll p=1; k>0; p*=2){
            ll cnt=min(k, p);
            items.push_back({cnt*v, cnt*w});
            k-=cnt;
        }
    }
    for(auto &item: items){
        for (ll j=s; j>=item.w; j--){
            dp[j]=max(dp[j], dp[j-item.w]+item.v);
        }
    }
    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: 0 / 27