Submission #979494

#	Time	Username	Problem	Language	Result	Execution time	Memory
979494		kilkuwu	Knapsack (NOI18_knapsack)	C++17	100 / 100	175 ms	40936 KiB

knapsack

#include <bits/stdc++.h>

#define nl '\n'

template <typename T>
inline bool ckmax(T& x, const T& y) {
  return x < y ? x = y, 1 : 0;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int S, N;
  std::cin >> S >> N;
  
  std::vector<std::map<int, int>> cnt(S + 1);

  for (int i = 0; i < N; i++) {
    int v, w, k;
    std::cin >> v >> w >> k;
    k = std::min(k, S / w);
    if (w <= S) {
      cnt[w][v] += k;
    }
  }

  std::vector<int> dp(S + 1);
  
  for (int i = 1; i <= S; i++) {
    int take_max = S / i;
    int sum = 0;
    for (auto& [v, k] : cnt[i]) {
      if (k >= 3) {
        int q = k - 1;
        k = 1 + (q & 1);
        if (2 * i <= S) {
          cnt[2 * i][2 * v] += q >> 1;
        }
      }
      sum += k;
    }

    for (auto [v, k] : cnt[i]) {
      if (sum - k <= take_max) {
        for (int x = 0; x < k; x++) {
          for (int j = S; j >= i; j--) {
            ckmax(dp[j], dp[j - i] + v);
          }
        }
      } 
      sum -= k;
    }

    // why wrong 
  }
  std::cout << dp[S] << nl;
}

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