Submission #870583

#	Time	Username	Problem	Language	Result	Execution time	Memory
870583		mall0809	Knapsack (NOI18_knapsack)	C++17	100 / 100	94 ms	3864 KiB

knapsack

#include <bits/stdc++.h>

#define C int(1e6+7)
#define M int(1e9+7)
#define el '\n'
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std;
typedef long long ll;

vector<array<int,2>> table[2002];
int dp[2002];
int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);cout.tie(0);
    //freopen("","r",stdin);
    //freopen("","w",stdout);

    int s,n;cin>>s>>n;
    for(int i=1;i<=n;i++){
        int v,w,k;cin>>v>>w>>k;
        table[w].pb({v,k});
    }
    vector<int> val,w;
    for(int i=1;i<=2000;i++){
        sort(all(table[i]),greater<>());
        int lim = s/i;
        for(int j=0;j<table[i].size() && lim>0;j++){
            for(int jj=1;jj<=table[i][j][1] && lim>0;jj++,lim--){
                val.pb(table[i][j][0]);
                w.pb(i);
            }
        }
    }
    for(int i=0;i<val.size();i++){
        for(int j=s;j >= w[i];j--)dp[j] = max(dp[j],dp[j-w[i]] + val[i]);
    }
    cout<<dp[s];
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j=0;j<table[i].size() && lim>0;j++){
      |                     ~^~~~~~~~~~~~~~~~
knapsack.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<val.size();i++){
      |                 ~^~~~~~~~~~~

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