Submission #1276069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276069		lee.desmond2016	Knapsack (NOI18_knapsack)	C++20	37 / 100	2 ms	588 KiB

knapsack

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

#define ll long long

const int MOD = 1e9+7;
const int INF = 1e9;

/**
 * https://oj.uz/problem/view/NOI18_knapsack
 * Classical Multiple Knapsack Problem
 * https://cp-algorithms.com/dynamic_programming/knapsack.html#multiple-knapsack
 * Idea:
 * Group items by weight, then sort by value descending since we want to take the most valuable items first.
 * Use 0-1 knapsack to decide how many items to take from each group.
 * dp[i][j] = max value using first i groups (weight type) with capacity j
 * time complexity: (S^2log(S))
 */
// void solve() {
//   int s, n;
//   cin >> s >> n;
//   map<int, vector<array<int, 2>>> mp;
//   for (int i = 0; i < n; i++) {
//     int v, w, k;
//     cin >> v >> w >> k;
//     if (w <= s) {
//       mp[w].push_back({v, k});
//     }
//   }  
//   vector<vector<ll>> dp(mp.size() + 1, vector<ll>(s + 1, -1));
//   dp[0][0] = 0;
//   int idx = 1;
//   // 0-1 knapsack
//   for (auto [w, v] : mp) {
//     sort(v.rbegin(), v.rend());
//     for (int i = 0; i <= s; i++) {
//       dp[idx][i] = dp[idx - 1][i];
//       int j = 0;
//       ll sumV = 0;
//       int cnt = 0;
//       int used = 0;
//       while (j < v.size() && (cnt + 1) * w <= i) {
//         cnt++;
//         sumV += v[j][0];
//         if (dp[idx - 1][i - cnt * w] != -1) {
//           dp[idx][i] = max(dp[idx][i], dp[idx - 1][i - cnt * w] + sumV);
//         }
//         used++;
//         if (used == v[j][1]) {
//           used = 0;
//           j++;
//         }
//       }
//     }
//     idx++;
//   }
//   ll ans = 0;
//   for (int i = 1; i <= s; i++) {
//     ans = max(ans, dp[mp.size()][i]);
//   }
//   cout << ans << '\n';
// }

void solve() {
  int s, n;
  cin >> s >> n;
  map<int, vector<array<int, 2>>> mp;
  for (int i = 0; i < n; i++) {
    int v, w, k;
    cin >> v >> w >> k;
    if (w <= s) {
      mp[w].push_back({v, k});
    }
  }
  vector<ll> dp(s + 1, 0);
  for (auto [w, ar]: mp) {
    sort(ar.rbegin(), ar.rend());
    for (auto [v, k] : ar) {
      for (int c = 1; k > 0; c <<= 1) {
        int take = min(k, c);
        for (int j = s; j >= w * take; j--) {
          dp[j] = max(dp[j], dp[j - w * take] + v * take);
        }
        k-= take;
      }
    }        
  }
  ll ans = *max_element(dp.begin(), dp.end());
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);

  // freopen("input.in", "r", stdin);
  // freopen("output.out", "w", stdout);

  // int T = 1;
  // cin >> T;
  // while (T--) {
    solve();
  // }

  return 0;
}

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