Submission #946729

#	Time	Username	Problem	Language	Result	Execution time	Memory
946729		hellowinchang1029	Knapsack (NOI18_knapsack)	C++17	100 / 100	55 ms	5580 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vvi vector<vector<int>>
#define vt vector
#define arr array
#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
const int MOD1=998244353;
const int MOD2=1e9+7;
const ll LINF=1e18;
const int INF=1e9;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    ll s, n;
    cin>>s>>n;
    map<ll, vt<pll>> items;
    for (ll i=0; i<n; i++){
    	ll v, w, k;
    	cin>>v>>w>>k;
    	items[w].pb({v, k});
    }
    vt<ll> dp(s+1, 0);
    vt<pll> use_items;
    for (ll i=1; i<=s; i++){
    	if (!items[i].size()) continue;
    	sort(rALL(items[i]));
    	for (ll j=0, id=0; j<=(s/i) && id<items[i].size(); j++){
    		use_items.pb({i, items[i][id].first});
    		if (!(--items[i][id].second)) id++;
    	}
    }
    for (pll item : use_items){
    	for (ll j=s; j>=item.first; j--){
    		dp[j]=max(dp[j], dp[j-item.first]+item.second);
    	}
    }
    cout<<dp[s]<<'\n';
    
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:35:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |      for (ll j=0, id=0; j<=(s/i) && id<items[i].size(); j++){
      |                                     ~~^~~~~~~~~~~~~~~~

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