Submission #970489

#	Time	Username	Problem	Language	Result	Execution time	Memory
970489		v_matei	Knapsack (NOI18_knapsack)	C++17	100 / 100	107 ms	2356 KiB

knapsack

#include <algorithm>
#include <iostream>
#include <vector>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define NMAX 100'007
#define SMAX 2007

int n, s;
std::vector<pii> bestW[SMAX];
std::vector<int> v, w;
int dp[SMAX];
void citire() {
  std::cin >> s >> n;
  int a, b, c;
  for (int i = 1; i <= n; i++) {
    std::cin >> a >> b >> c;
    bestW[b].push_back({a, c});
  }
}

int main() {
  citire();

  for (int i = 1; i <= s; i++) {
    std::sort(bestW[i].begin(), bestW[i].end());
    for (int j = 0; j < s && !bestW[i].empty(); j += i) {
      v.push_back(bestW[i].back().first);
      w.push_back(i);
      if (!--bestW[i].back().second)
        bestW[i].pop_back();
    }
  }
  n = v.size();
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = s; j >= w[i]; j--) {
      dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
    }
  }

  std::cout << dp[s];
  return 0;
}

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