제출 #1196544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196544		i_liek_cheezits	Knapsack (NOI18_knapsack)	C++20	100 / 100	66 ms	33108 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  int s, n; cin >> s >> n;
  map<int, vector<pii>> cnt; 
  for(int i = 0; i < n; i++) {
      int v, w, k; cin >> v >> w >> k;
      if (w <= s && k) cnt[w].push_back({v, k}); 
  }
  vector<vector<ll>> dp(sz(cnt)+1, vector<ll>(s+1, INT_MIN)); 
  dp[0][0] = 0; 
  int curr = 1; 
  for(auto &[w, v] :  cnt) {
      sort(all(v)); reverse(all(v)); 
      for(int i = 0; i <= s; i++) {
          dp[curr][i] = dp[curr-1][i]; 
          int idx = 0; int num = 0; int curr_num = 0;  
          ll money = 0; 
          while(1ll * (num+1) * w <= i && idx < sz(v)) {
              num++;
              money += v[idx].f; 
              if (dp[curr-1][i - num * w] != INT_MIN) {
                  dp[curr][i] = max(dp[curr][i], dp[curr-1][i - num * w] + money); 
              }
              curr_num++; 
              if(curr_num == v[idx].s) {
                  curr_num = 0; idx++; 
              }
          }
      }
      curr++; 
  }
  cout << *max_element(all(dp.back())) << "\n"; 
  return 0;
}

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