Submission #1258912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258912		sumu16	Knapsack (NOI18_knapsack)	C++20	100 / 100	132 ms	11564 KiB

knapsack

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

int32_t main() {

   int S, N;
   cin >> S >> N;
   vector<int>val(N);
   vector<int>wt(N);
   vector<int>k(N);
   map<int, vector<int>>m;
   for(int i = 0; i<N; ++i)
   {
       cin >> val[i] >> wt[i] >> k[i];
       int limit = min(S/wt[i], k[i]);
       for(int j = 1; limit>0; j<<=1)
       {
           int p = min(j, limit);
           int weight = p*wt[i];
           int value = p*val[i];
           m[weight].push_back(value);
           limit-=p;
       }
   }

   vector<pair<int, int>>final_items;
   for(auto& [w, vals]: m)
   {
       int cnt = S/w;
       int sz = vals.size();

       if(sz>cnt)
       {
           sort(vals.begin(), vals.end(), greater<>());
           vals.resize(cnt);
       }
       for(int it : vals)
       {
           final_items.push_back({w,it});
       }
   }

   vector<int>dp(S+1, 0);
   for(auto& [it1, it2] : final_items)
   {
       for(int j = S; j>=it1; --j)
       {
           dp[j] = max(dp[j], dp[j-it1] + it2);
       }
   }
   cout << dp[S];
    return 0;
}

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