Submission #1370587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370587		luka2881	Knapsack (NOI18_knapsack)	C++20	12 / 100	0 ms	344 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int s,n;
    cin>>s>>n;
    vector<int>v(n);
    vector<int>w(n);
    vector<int>k(n);
    vector<int>dp(s+1,0);
    for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>k[i];
    vector<vector<pair<int,int>>>p(s+1);
    sort(p.begin(),p.end());
    reverse(p.begin(),p.end());
    vector<pair<int,int>>a;
    for(int i=0;i<n;i++)
    {
        p[w[i]].push_back(make_pair(v[i],k[i]));
    }
    for(int i=1;i<=s;i++)
    {
        int uk=0;
        int j=0;
        while(j<p[i].size())
        {
            int k=0;
            while(k<p[i][j].second)
            {
                a.push_back(make_pair(p[i][j].first,i));
                k++;
                uk++;
                if(uk>s/i)break;
            }
            if(uk>s/i)break;
            j++;
        }
    }
    for(int i=0;i<a.size();i++)
    {
        vector<int>dppom(s+1);
        for(int j=a[i].second;j<=s;j++)
        {
            dppom[j]=max(dp[j],dp[j-a[i].second]+a[i].first);
        }
        dp=dppom;
    }
    cout<<dp[s]<<endl;
}

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