Submission #906293

#	Time	Username	Problem	Language	Result	Execution time	Memory
906293		nicyzk	Knapsack (NOI18_knapsack)	C++14	100 / 100	202 ms	248004 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18

void solve() {
    ll S,N; cin>>S>>N; 
    map<ll,vector<pair<ll,ll>>> m; // wt: [[val,cnt]]
    for (ll i=0; i<N; i++) {
        ll V,W,K; cin>>V>>W>>K; 
        m[W].push_back({V,K}); 
    }
    for (auto &x: m) {
        sort(x.second.rbegin(), x.second.rend()); 
    }
    vector<pair<ll,ll>> items; 
    for (auto x:m) {
        ll wt = x.first; 
        ll cnt = S/wt; 
        ll done = 0; 
        for (ll i=0; i<x.second.size(); i++) {
            ll val = x.second[i].first; 
            ll ttl = x.second[i].second; 
            for (ll j=0; j<ttl; j++) {
                items.push_back({val, wt}); 
                cnt--; 
                if (cnt == 0) {
                    done = 1; break; 
                }
            }
            if (done == 1) break; 
        }
    }
    vector<vector<ll>> dp(items.size()+1, vector<ll>(S+1,0)); 
    for (ll i=1; i<=items.size(); i++) {
        for (ll j=1; j<=S; j++) {
            if (j - items[i-1].second >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-items[i-1].second] + items[i-1].first); 
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]); 
        }
    }
    cout << dp[items.size()][S] << endl; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve(); 
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:21:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (ll i=0; i<x.second.size(); i++) {
      |                      ~^~~~~~~~~~~~~~~~
knapsack.cpp:35:19: warning: comparison of integer expressions of different signedness: 'll' {aka '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 i=1; i<=items.size(); i++) {
      |                  ~^~~~~~~~~~~~~~

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