제출 #401388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401388		Alex_tz307	Knapsack (NOI18_knapsack)	C++17	100 / 100	70 ms	5500 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

struct item {
  int v, w, k;

  void read() {
    cin >> v >> w >> k;
  }

  bool operator < (const item &A) const {
    if (v != A.v)
      return v > A.v;
    return k > A.k;
  }
};

void max_self(int &a, int b) {
  a = max(a, b);
}

void test_case() {
  int S, N;
  cin >> S >> N;
  vector<item> a(N), wt[S + 1];
  for (int i = 0; i < N; ++i) {
    a[i].read();
    wt[a[i].w].emplace_back(a[i]);
  }
  vector<pair<int,int>> v;
  for (int w = 0; w <= S; ++w)
    if (!wt[w].empty()) {
      sort(wt[w].begin(), wt[w].end());
      int p = 0, sum = 0;
      while (p < (int)wt[w].size() && sum <= S) {
        int lim = min(wt[w][p].k, (S - sum) / wt[w][p].w);
        sum += w * lim;
        for (int i = 0; i < lim; ++i)
          v.emplace_back(wt[w][p].v, wt[w][p].w);
        ++p;
      }
    }
  vector<int> dp(S + 1);
  for (auto p : v) {
    int v = p.first, w = p.second;
    for (int wt = S - w; wt >= 0; --wt)
      max_self(dp[wt + w], dp[wt] + v);
  }
  int ans = 0;
  for (int w = 1; w <= S; ++w)
    max_self(ans, dp[w]);
  cout << ans << '\n';
}

void solve() {
  int T = 1;
  for (int tc = 0; tc < T; ++tc)
    test_case();
}

int main() {
  fastIO();
  solve();
  return 0;
}

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