제출 #1127005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127005		himanshu_03	Knapsack (NOI18_knapsack)	C++17	100 / 100	123 ms	17608 KiB

knapsack

#include "bits/stdc++.h"
using namespace std;

//cycle edges = total edges-bridge edges
// adding cycle edges does not decrease the number of disconnected component but bridge edges do
// decreasing order of weight of edges . adding using dsu -> edges whoes parent already in the component is the cycle edges->can be found the min. weight prsent in cycle


const int md=1e9+7;
int main()
{
    int s,n;
    cin>>s>>n;
    map<int,vector<pair<int,int > > > mp;
    for(int i=1;i<=n;i++){
        int vl,we,no;
        cin>>vl>>we>>no;
        if(we<=s && no>0){
            mp[we].push_back(make_pair(vl,no));
        }
    }
    vector<vector<int> > dp(mp.size()+1,vector<int>(s+1,0));

    int st=1;
    for(auto [w, items]:mp){

        sort(items.begin(),items.end(),greater<pair<int,int> >());
        for(int i=0;i<=s;i++){
            dp[st][i]=dp[st-1][i];
            int taken=0;
            int subcls=0;
            int curr_taken=0;
            int addi=0;

            while((taken+1)*w<=i && subcls<items.size()){
               taken++;
               addi+=items[subcls].first;
                dp[st][i]=max(dp[st][i],dp[st-1][i-taken*w]+addi);

                curr_taken++;
                if(curr_taken==items[subcls].second){
                    curr_taken=0;
                    subcls++;
                }
            }

        }
        st++;
    }    
  
    int maxv=0;
    for(int i=0;i<=mp.size();i++){
        maxv=max(maxv,dp[i][s]);
    }

    cout<<maxv<<endl;

    


   
    
   


    return 0;
}

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