Submission #1052789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052789		kflippy	Knapsack (NOI18_knapsack)	C++17	100 / 100	77 ms	35188 KiB

knapsack

#include <bits/stdc++.h>

int32_t main() {
  int32_t S, N;
  std::cin >> S >> N;
  std::vector<int64_t> dp(S + 1, -1);
  dp[0] = 0;
  std::vector<std::vector<std::pair<int32_t, int32_t>>> wCnt(S + 1, std::vector<std::pair<int32_t, int32_t>>());
  for(int32_t i = 0; i < N; i++) {
    int32_t V, W, K;
    std::cin >> V >> W >> K;
    wCnt[W].push_back({V, K});
  }
  for(int32_t i = 0; i <= S; i++) {
    sort(wCnt[i].begin(), wCnt[i].end(), std::greater<std::pair<int32_t, int32_t>>());
  }
  std::vector<std::vector<std::pair<int32_t, int32_t>>> kCnt(S + 1, std::vector<std::pair<int32_t, int32_t>>(S + 1));
  std::vector<int32_t> take(S + 1);
  for(int32_t j = 0; j < S; j++) {
    if(j != 0) {
    for(int32_t i = 1; i <= S; i++) {
      if(wCnt[i].size() == 0) continue;
        if(i != take[j]) kCnt[j][i] = kCnt[j - take[j]][i];
        else {
          kCnt[j][i].first = kCnt[j - take[j]][i].first + 1;
          kCnt[j][i].second = kCnt[j - take[j]][i].second;
          if(kCnt[j][i].first >= wCnt[i][kCnt[j][i].second].second) {
            kCnt[j][i].first = 0;
            kCnt[j][i].second++;
            // std::cout << "kill me\n";
            // std::cout << kCnt[j][i].first << " " << kCnt[j][i].second << "\n";
          }
          if(kCnt[j][i].second >= wCnt[i].size()) {
            // std::cout << "something WRONG IS HAPPENING\n";
            kCnt[j][i] = {-1, -1};
          }
        }
      }
    }
    if(dp[j] == -1) continue;
    for(int i = 1; i <= S; i++) {
      if(j + i > S) break;
      if(wCnt[i].size() == 0 || kCnt[j][i].second == -1) continue;
      if(dp[i + j] < dp[j] + wCnt[i][kCnt[j][i].second].first) {
        // std::cout << "before: " << dp[i + j] << "\n";
        dp[i + j] = dp[j] + wCnt[i][kCnt[j][i].second].first;
        // std::cout << "after: " << dp[i + j] << "\n";
        // std::cout << dp[j] << " " << wCnt[i][kCnt[j][i].second].first << "\n";
        // std::cout << "dp[i + j]: " << "i = " << i << ", j = " << j << " = " << dp[i + j] << "\n";
        take[i + j] = i;
      }
    }
  }
  int64_t ans = 0;
  for(int32_t i = 0; i <= S; i++) {
    // std::cout << i << ": " << dp[i] << " " << take[i] << "\n";
    if(dp[i] != -1) ans = std::max(ans, dp[i]);
  }
  // std::cout << "\n";
  std::cout << ans << "\n";
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:33:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |           if(kCnt[j][i].second >= wCnt[i].size()) {

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