제출 #1194017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194017		dungtt	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	504 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int S, N;
  cin >> S >> N;
  vector<ll> dp(S+1, 0);

  for(int i = 0; i < N; i++){
    ll V, W, K;
    cin >> V >> W >> K;

    // 1) Complete knapsack nếu đủ nhiều
    if (K * W >= S) {
      for(int j = W; j <= S; j++){
        dp[j] = max(dp[j], dp[j - W] + V);
      }
      continue;
    }

    // 2) Bounded knapsack: copy dp sang old
    vector<ll> old = dp;

    // Xử lý từng residue class r = 0..W-1
    for(int r = 0; r < W; r++){
      deque<pair<int,ll>> deq;
      // t_max sao cho j = r + t*W ≤ S
      int t_max = (S - r) / W;
      for(int t = 0; t <= t_max; t++){
        int j = r + t * W;

        // Loại khỏi front các u < t-K
        while(!deq.empty() && deq.front().first < t - K)
          deq.pop_front();

        // Tính dp[j]: không lấy món nào mới là old[j]
        ll best = old[j];
        if (!deq.empty()) {
          // hoặc lấy thêm (t - u) món => deq.front().second + t*V
          best = max(best, deq.front().second + t * V);
        }
        dp[j] = best;

        // Tạo giá trị A_t = old[j] - t*V để phục vụ tương lai
        ll At = old[j] - t * V;
        // Trước khi push, pop_back các phần tử ≤ At
        while(!deq.empty() && deq.back().second <= At)
          deq.pop_back();
        deq.emplace_back(t, At);
      }
    }
  }

  // Kết quả: dp[j] là max giá trị với trọng số = j
  // nếu cần ≤ S thì lấy max dp[0..S]
  ll ans = 0;
  for(int j = 0; j <= S; j++)
    ans = max(ans, dp[j]);
  cout << ans << "\n";
  return 0;
}

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