Submission #970983

#	Time	Username	Problem	Language	Result	Execution time	Memory
970983		handlename	Knapsack (NOI18_knapsack)	C++17	100 / 100	44 ms	3160 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
int s,n;
int memo[2001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>s>>n;
    multiset<int> arr[s+1];
    for (int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        c=min(c,s/b);
        while (c>0 && arr[b].size()+1<=s/b){
            arr[b].insert(a);
            c--;
        }
        while (c>0 && a>(*arr[b].begin())){
            arr[b].erase(arr[b].begin());
            arr[b].insert(a);
            c--;
        }
    }
    for (int b=0;b<=s;b++){
        for (auto a:arr[b]){
            for (int j=s-b;j>=0;j--){
                memo[j+b]=max(memo[j+b],memo[j]+a);
            }
        }
    }
    cout<<memo[s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:38: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   14 |         while (c>0 && arr[b].size()+1<=s/b){
      |                       ~~~~~~~~~~~~~~~^~~~~

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