Submission #734127

#	Time	Username	Problem	Language	Result	Execution time	Memory
734127		swapbeast	Knapsack (NOI18_knapsack)	C++14	100 / 100	141 ms	3780 KiB

knapsack

//https://oj.uz/problem/view/NOI18_knapsack

#include<bits/stdc++.h>

using namespace std;
#define pb push_back
#define ll long long
#define MAXN 2001
ll dp[2][MAXN];
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
int main()
{
    int n,S;cin>>S>>n;
    vector<vector<pair<int,int>>>vec(MAXN);
    for(int i=0;i<n;i++)
    {
        int V,W,K;cin>>V>>W>>K;
        vec[W].pb({V,K});
    }

    vector<int>w,v;
    for(int i=1;i<MAXN;i++)
    {
        if((int)vec[i].size()==0)continue;

        sort(rall(vec[i]));
        int j=S/i;
        int k=0;
        while(j&&k<vec[i].size())
        {
            w.pb(i);
            v.pb(vec[i][k].first);
            j--;
            vec[i][k].second--;
            if(vec[i][k].second==0)k++;
        }
    }
    memset(dp,0,sizeof(dp));
    int m = w.size();
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<=S;j++)
        {
            if(j+w[i]<=S)
                dp[(i+1)%2][j+w[i]]=max(dp[(i+1)%2][j+w[i]],v[i]+dp[i%2][j]);
            dp[(i+1)%2][j]=max(dp[(i+1)%2][j],dp[i%2][j]);
        }
    }

    cout<<dp[m%2][S];


}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while(j&&k<vec[i].size())
      |                  ~^~~~~~~~~~~~~~

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