Submission #1254814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254814		orny_nabila	Knapsack (NOI18_knapsack)	C++20	73 / 100	374 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);
   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]);
       }
   }
   /*
   for(auto& [w, vals]:m)
   {
       cout << w << endl;
       for(int v : vals)
       {
           cout << v << " ";
       }
       cout << endl;
   }
   cout << endl;
   */
   vector<pair<int, int>>final_items;
   for(auto& [w, vals]: m)
   {
       int cnt = S/w;
       int sz = vals.size();
      // cout << "cnt: " << cnt << " sz: " << sz << endl;
       if(sz>cnt)
       {
           sort(vals.begin(), vals.end(), greater<>());
           vals.resize(cnt);
       }
       for(int it : vals)
       {
           final_items.push_back({w,it});
       }
   }
   /*
   for(auto& [i, j]: final_items)
   {
       cout << i << " " << j << endl;
   }
   */
   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