Submission #1036272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036272		ind1v	Knapsack (NOI18_knapsack)	C++11	100 / 100	39 ms	4956 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int S = 2e3 + 5;

int s, n;
int v[N], w[N], k[N];
priority_queue<pair<int, int>> pq[S];
vector<pair<int, int>> obj;
int f[S];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i] >> w[i] >> k[i];
    pq[w[i]].push({v[i], k[i]});
  }
  for (int i = 1; i <= s; i++) {
    int cur = s;
    while (!pq[i].empty() && cur - i >= 0) {
      int u = pq[i].top().first;
      int cnt = pq[i].top().second;
      obj.emplace_back(i, u);
      pq[i].pop();
      cnt--;
      if (cnt > 0) {
        pq[i].push({u, cnt});
      }
      cur -= i;
    }
  }
  memset(f, -0x3f, sizeof(f));
  f[0] = 0;
  for (auto x : obj) {
    for (int i = s; i - x.first >= 0; i--) {
      f[i] = max(f[i], f[i - x.first] + x.second);
    }
  }
  cout << *max_element(f, f + s + 1) << '\n';
  return 0;
}

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