Submission #979490

#	Time	Username	Problem	Language	Result	Execution time	Memory
979490		kilkuwu	Knapsack (NOI18_knapsack)	C++17	73 / 100	1058 ms	29008 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<std::pair<int, int>> items;
  std::vector<int> dp(S + 1);
  
  for (int i = 1; i <= S; i++) {
    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;
        }
      }
      while (k--) {
        for (int j = S; j >= i; j--) {
          ckmax(dp[j], dp[j - i] + v);
        }
      }
    }
  }

  std::cout << dp[S] << nl;
}

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