Submission #971937

#	Time	Username	Problem	Language	Result	Execution time	Memory
971937		malkhuzanie	Knapsack (NOI18_knapsack)	C++17	100 / 100	123 ms	129292 KiB

knapsack

#include <bits/stdc++.h>

#ifdef LOCAL
#include "/home/tomato/pr/include/debug.h"
#include "/home/tomato/pr/include/utils.h"
#else
#define debug(...)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  constexpr int _max_s = 2000;
  constexpr int inf = -1e0;
  int s, n;
  cin >> s >> n;
  vector<map<int, int>> v(_max_s + 1);
  for (int i = 0; i < n; ++i) {
    int val, w, k;
    cin >> val >> w >> k;
    v[w][val] += k;
  }
  vector<pair<int, int>> wgt;
  for (int i = 1; i <= s; ++i) {
    int rem = s / i;
    for (auto it = v[i].rbegin(); rem && it != v[i].rend(); ++it) {
      for (int j = 0; j < min(rem, it->second); ++j) {
        wgt.emplace_back(i, it->first);
      }
      rem -= min(rem, it->second);
    }
  }
  vector<vector<int>> dp(wgt.size() + 1, vector<int>(s + 1, -1));
  dp[0][0] = dp[0][1] = 0;
  for (int i = 1; i <= (int)wgt.size(); ++i) {
    for (int j = 0; j <= s; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (j >= wgt[i - 1].first) {
        int r = i - 1;
        dp[i][j] = max(dp[i][j], dp[i - 1][j - wgt[r].first] + wgt[r].second);
      }
    }
  }
  int l = wgt.size();
  cout << *max_element(dp[l].begin(), dp[l].end());
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:16:17: warning: unused variable 'inf' [-Wunused-variable]
   16 |   constexpr int inf = -1e0;
      |                 ^~~

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