Submission #888972

#	Time	Username	Problem	Language	Result	Execution time	Memory
888972		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	56 ms	5072 KiB

knapsack

#include <bits/stdc++.h>
typedef long long ll;
#define endl "\n"
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const ll maxN=2000+10;
ll dp[maxN+1];
ll cnt[maxN+1];
struct items
{
    ll w,v,cnt;
};
bool cmp(items x,items y)
{
    if(x.w!=y.w)
        return x.w<y.w;
    if(x.v!=y.v)
        return x.v>y.v;
    return x.cnt>y.cnt;
}
vector<items> ok;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    ll n,s;
    cin>>s>>n;
    for(ll i=1;i<=n;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        ok.push_back({b,a,c});
    }
    for(ll i=1;i<=s;i++)
        cnt[i]=s/i;
    sort(ok.begin(),ok.end(),cmp);
    vector<pii> item;
    for(ll i=0;i<ok.size();i++)
    {
        ll w=ok[i].w;
        ll c=ok[i].cnt;
        ll v=ok[i].v;
        while(cnt[w]>0 && c>0)
        {
            item.push_back({w,v});
            cnt[w]--;
            c--;
        }
    }
    for(ll i=1;i<=s;i++)
        dp[i]=-1;
    for(auto i:item)
        for(ll j=s;j>=i.fi;j--)
        {
            if(dp[j-i.fi]==-1)
                continue;
            dp[j]=max(dp[j],dp[j-i.fi]+i.se);
        }
    ll ans=dp[0];
    for(ll i=1;i<=s;i++)
        ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<items>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(ll i=0;i<ok.size();i++)
      |                ~^~~~~~~~~~

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