Submission #1198211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198211		almaharbas4	Knapsack (NOI18_knapsack)	C++20	100 / 100	103 ms	36764 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n,k;
    cin>>k>>n;
    vector<ll> val(n),w(n),cap(n);
    map<ll,vector<pair<ll,ll>>> mapa;
    for(int i=0;i<n;i++)
    {
        cin>>val[i]>>w[i]>>cap[i];
        mapa[w[i]].push_back({val[i],cap[i]});
    }
    vector<vector<ll>> dp(mapa.size()+1,vector<ll>(k+1,INT32_MIN));
    dp[0][0]=0;
    ll at=1;
    for(auto &[a,v]:mapa)
    {
        sort(v.rbegin(),v.rend());
        for(int i=0;i<=k;i++)
        {
            dp[at][i]=dp[at-1][i];
            ll copies=0;
            ll typeat=0;
            ll profit=0;
            ll curused=0;
            while((copies+1)*a<=i&&typeat<v.size())
            {
                copies++;
                profit+=v[typeat].first;
                if(dp[at-1][i-a*copies]!=INT32_MIN)
                {
                    dp[at][i]=max(dp[at][i],dp[at-1][i-a*copies]+profit);
                }
                curused++;
                if(curused==v[typeat].second)
                {
                    curused=0;
                    typeat++;
                }
            }
        }
        at++;
    }
    cout<<*max_element(dp.back().begin(),dp.back().end())<<endl;
    return 0;
}

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