Submission #629394

#	Time	Username	Problem	Language	Result	Execution time	Memory
629394		huyle	Knapsack (NOI18_knapsack)	C++17	100 / 100	71 ms	4044 KiB

knapsack

#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 69
#endif
const i64 inf = 1e18;
int32_t main() {
  int s, n;
  scanf("%d %d", &s, &n);
  std::vector<std::vector<std::pair<int, int>>> a(s + 1);
  std::vector<int> wei(n);
  for (int i = 0; i < n; ++i) {
    int v, w, k;
    scanf("%d %d %d", &v, &w, &k);
    a[w].push_back({v, k});
    wei[i] = w;
  }
  for (int i = 0; i <= s; ++i)
    std::sort(a[i].rbegin(), a[i].rend());
  std::sort(wei.begin(), wei.end());
  wei.resize(std::unique(wei.begin(), wei.end()) - wei.begin());
  n = (int)wei.size();
  std::vector<i64> dp(s + 1, -inf);
  dp[0] = 0;
  for (int ii = 0; ii < n; ++ii) {
    int i = wei[ii];
    for (int j = s; ~j; --j) {
      if (dp[j] == -inf)
        continue;
      int cnt = 0, idx = 0, res = 0, total = 0;
      while (idx < (int)a[i].size()) {
        res += a[i][idx].first;
        ++cnt;
        ++total;
        if (j + (i64)total * i > s)
          break;
        dp[j + total * i] = std::max(dp[j + total * i], dp[j] + res);
        if (cnt == a[i][idx].second) {
          cnt = 0;
          ++idx;
        }
      }
    }
  }
  printf("%lld\n", *std::max_element(dp.begin(), dp.end()));
}

Compilation message (stderr)

knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   scanf("%d %d", &s, &n);
      |   ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d %d %d", &v, &w, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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