Submission #1090226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090226		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	58 ms	5572 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=2001;
struct items
{
    ll w,v,cnt;
};
vector<items> item;
bool cmp(items a,items b)
{
    return a.v>b.v;
}
ll s,n;
ll lef[maxN+1];
ll dp[maxN+1];
ll vi[maxN+1];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    cin>>s>>n;
    for(ll i=1;i<=n;i++)
    {
        ll w,v,cnt;
        cin>>v>>w>>cnt;
        item.push_back({w,v,cnt});
    }
    sort(item.begin(),item.end(),cmp);
    for(ll i=1;i<=s;i++)
        lef[i]=s/i;
    vector<items> kul;
    for(auto i:item)
    {
        if(lef[i.w]==0)
            continue;
        ll ok=min(lef[i.w],i.cnt);
        lef[i.w]-=ok;
//        cout<<"aa "<<i.w<<" "<<i.v<<endl;
        while(ok--)
            kul.push_back({i.w,i.v,1});
    }
    vi[0]=1;
    for(auto i:kul)
    {
//        cout<<i.w<<" "<<i.v<<" ________________"<<endl;
        for(ll j=maxN;j>=i.w;j--)
            if(vi[j-i.w]==1)
            {
//                cout<<j<<" "<<i.w<<" "<<i.v<<" ";
                dp[j]=max(dp[j],dp[j-i.w]+i.v);
//                cout<<dp[j]<<endl;
                vi[j]=1;
            }
    }
    ll ans=0;
    for(ll i=1;i<=s;i++)
        ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

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