제출 #1254819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254819		orny_nabila	Knapsack (NOI18_knapsack)	C++20	73 / 100	390 ms	327680 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);
   unordered_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 = 0; j<limit; ++j)
       {
           m[wt[i]].push_back(val[i]);
       }
   }
   
   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: 0 / 27