Submission #892716

#	Time	Username	Problem	Language	Result	Execution time	Memory
892716		hanlei35	Knapsack (NOI18_knapsack)	C++17	100 / 100	57 ms	5200 KiB

knapsack

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct item{
    int w;
    ll v, k;
};

ll dp[2001];
vector<ll> vals[2001];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int S, N; cin >> S >> N;
    vector<item> items = vector<item>(N);
    for(int i=0;i<N;i++) cin >> items[i].v >> items[i].w >> items[i].k;
    sort(items.begin(), items.end(), 
        [](const item &x, const item &y){ return x.v > y.v; });
    
    for(int i=0;i<N;i++){
        int sz = items[i].w; ll val = items[i].v, cnt = items[i].k;
        while(vals[sz].size() + 1 <= (S / sz) && cnt){
            vals[sz].push_back(val);
            cnt--;
        }
    }
    
    for(int i=1;i<=S;i++){
        for(auto x:vals[i]){
            for(int j=S;j>i;j--){
                dp[j] = max(dp[j], dp[j - i] + x);
            }
            dp[i] = max(dp[i], dp[0] + x);
        }
    }
    
    ll mx = -1;
    for(int i=0;i<=S;i++) mx = max(mx, dp[i]);
    cout << mx << "\n";
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:31:35: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         while(vals[sz].size() + 1 <= (S / sz) && cnt){
      |               ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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