제출 #1205512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205512		loom	Knapsack (NOI18_knapsack)	C++20	100 / 100	44 ms	2884 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

inline void solve(){
   int s, n;
   cin>>s>>n;
   vector<pair<int,int>> a[s+1];
   for(int i=0; i<n; i++){
      int v, w, k;
      cin>>v>>w>>k;
      a[w].push_back({v, k});
   }

   vector<int> ldp(s+1, 0), dp(s+1);

   for(int w=1, i=0; w<=s; w++){
      sort(a[w].rbegin(), a[w].rend());

      int c = 0;
      for(auto [v, k] : a[w]){
         for(; k > 0 and c < s/w; i++, c++, k--){
            for(int j=0; j<=s; j++){
               dp[j] = ldp[j];
               if(j-w >= 0) dp[j] = max(dp[j], ldp[j-w] + v);
            }

            swap(ldp, dp);
         }
      }
   }

   cout<<ldp[s];
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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