Submission #1241824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241824		ak5028	Knapsack (NOI18_knapsack)	C++20	100 / 100	102 ms	34696 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
typedef long long  int ll;

int main(){
   ll s,n;cin>>s>>n;
   map<ll,vector<pair<ll,ll>>>diff_wts;
   for(ll i=1;i<=n;i++){
      ll v,w,k;
      cin>>v>>w>>k;
      diff_wts[w].push_back({v,k});
   }
   vector<vector<ll>>dp(diff_wts.size()+1,vector<ll>(s+1));
   dp[0][0]=0;
   ll i=1;
   for(auto &val:diff_wts){
      ll wt=val.first;
      vector<pair<ll,ll>>item_info=val.second;
      sort(item_info.begin(),item_info.end(),greater<pair<ll,ll>>());
      for(ll j=0;j<=s;j++){
         dp[i][j]=dp[i-1][j];
         ll copies=0;
         ll type_at=0;
         ll curr_used=0;
         ll profit=0;
         while(type_at < item_info.size() && j -(copies+1)*wt >=0){
               copies++;//yeh copies always increase until in while loop
               profit += item_info[type_at].first; //profit also getting increase until in while loop
               dp[i][j]=max(dp[i][j] ,dp[i-1][j -copies*wt]+profit);
               curr_used++;//to check for one type completion so that move to another type
               if(curr_used==item_info[type_at].second){
                  type_at++;//move to next type means move to next pair of item_info
                  curr_used=0;
               }
         }
      }
      i++;
   }
   //cout<<dp[diff_wts.size()][s];
   auto it=*max_element(dp.back().begin(), dp.back().end());
   cout<<it;
}

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