Submission #1322677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322677		adiat	Knapsack (NOI18_knapsack)	C++20	29 / 100	11 ms	15836 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
    int w;
    int v;
    int k;
};
signed main()
{
    int s,n;
    cin>>s>>n;
    vector<int> v;
    map<int,int> mp;
    vector<priority_queue<pair<int,int>>> pq(2000);
    for(int i=0; i<n; i++)
    {
        int w,vl,k;
        cin>>vl>>w>>k;
        if(w>2000) continue;
        k=min(k, s/w);
        if(!mp[w]) v.push_back(w);
        // k=min(k, (s/w)-mp[w]);
        // if(k==0) continue;
        pq[w].push({vl,k});
        // mp[w]+=k;
    }
    sort(v.begin(), v.end());
    map<int, map<int,int>> cost;
    vector<int> wt, val;
    for(int i: v)
    {
        int ss=s/i;
        while(!pq[i].empty())
        {
            for(int j=0; j<min(ss,pq[i].top().second); j++)
            {
                wt.push_back(i);
                val.push_back(pq[i].top().first);
            }
            ss-=min(ss,pq[i].top().second);
            pq[i].pop();
        }
    }
    vector<vector<int>> dp(wt.size()+1, vector<int> (s+1, 0));
    // for(int i: wt) cout<<i<<" ";
    // cout<<endl;
    // for(int i: val) cout<<i<<" ";
    // cout<<endl;
    for(int i=1; i<=wt.size(); i++)
    {
        for(int j=1; j<=s; j++)
        {
            if(j<wt[i-1])
            {
                dp[i][j]=dp[i-1][j];
            }
            else
            { 
                dp[i][j]=dp[i-1][j];
                if(j-wt[i-1]>=0)
                    dp[i][j]=max(dp[i][j], dp[i-1][j-wt[i-1]]+val[i-1]);
            }
        }
    }
    int ans=0;
    // for(auto i: dp)
    // {
    //     for(auto j: i)
    //         cout<<j<<" ";
    //     cout<<endl;
    // }
    for(int i=0; i<dp.size(); i++)
    {
        for(int j=0; j<dp[i].size(); j++)
        {
            ans=max(ans, dp[i][j]);
        }
    }
    cout<<ans<<endl;
}

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