Submission #844779

#	Time	Username	Problem	Language	Result	Execution time	Memory
844779		qrno	Knapsack (NOI18_knapsack)	C++17	100 / 100	44 ms	4952 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int S, N;
  cin >> S >> N;

  vector<vector<pair<int, int>>> W(S+1);
  for (int i = 0; i < N; i++) {
    int v, w, k;
    cin >> v >> w >> k;
    W[w].push_back({v, k});
  }

  vector<int> M(S+1);
  for (int w = 1; w <= S; w++) {
    sort(rbegin(W[w]), rend(W[w]));
    int left = S/w;
    for (auto [v, k] : W[w]) {
      while (left && k) {
        for (int i = S; i-w >= 0; i--)
          M[i] = max(M[i], M[i-w]+v);
        k--, left--;
      }
      if (!left) break;
    }
  }

  cout << *max_element(begin(M), end(M)) << endl;
}

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