Submission #1281186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281186		AtinaR	Knapsack (NOI18_knapsack)	C++20	100 / 100	112 ms	17496 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
int s,n;
const int MAX=1e5+10;
map<int,vector<pair<int,int> > > by_weight;
int main()
{
    cin>>s>>n;
    for(int i=0; i<n; i++)
    {
        int weight,value,quantity;
        cin>>value>>weight>>quantity;
        by_weight[weight].push_back({value,quantity});
    }
    int dp[by_weight.size()+1][s+1];
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    int idx=1;
    int ans=0;
    for(auto &[w, items]:by_weight)
    {
        sort(items.begin(),items.end());
        reverse(items.begin(),items.end());
        for(int cap=0; cap<=s; cap++)
        {
            dp[idx][cap]=dp[idx-1][cap];
            int cp=0;
            int cnt=0;
            int total=0;
            int sum=0;
            while((cp+1)*w<=cap && cnt<items.size())
            {
                cp++;
                sum+=items[cnt].first;
                if(dp[idx-1][cap-cp*w]!=-1)
                {
                    dp[idx][cap]=max(dp[idx-1][cap-cp*w]+sum,dp[idx][cap]);
                }
                total++;
                if(total==items[cnt].second)
                {
                    total=0;
                    cnt++;
                }
                ans=max(ans,dp[idx][cap]);
            }
        }
        idx++;
    }
    cout<<ans<<endl;
    return 0;
}

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