Submission #1146273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146273		LeonidCuk	Knapsack (NOI18_knapsack)	C++20	100 / 100	74 ms	2060 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int>&a,pair<int,int>&b)
{
    return a.first>b.first;
}
int main()
{
    int k,n,a,b,c;
    cin>>k>>n;
    vector<pair<int,int>>v[k+1];
    long long int dp[k+1]={0};
    for(int i=0;i<n;i++)
    {
        cin>>a>>b>>c;
        v[b].push_back({a,c});
    }
    for(int i=0;i<=k;i++)
    {
        sort(v[i].begin(),v[i].end(),cmp);
    }
    for(int i=1;i<=k;i++)
    {
        if(v[i].size()==0)continue;
        for(int j=k;j>=i;j--)
        {
            int l=0,sum=0,t=v[i][0].second,sum1=0;
            while(j-sum1>=0)
            {
                dp[j]=max(dp[j],dp[j-sum1]+sum);
                if(t==0)
                {
                    l++;
                    if(l==v[i].size())break;
                    t=v[i][l].second;
                }
                sum1+=i;
                sum+=v[i][l].first;
                t--;
            }
        }
    }
    cout<<dp[k];
    return 0;
}

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