Submission #1276026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276026		lee.desmond2016	Knapsack (NOI18_knapsack)	C++20	100 / 100	68 ms	33304 KiB

knapsack

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

#define ll long long

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

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;
  for (auto [w, v] : mp) {
    sort(v.rbegin(), v.rend());
    // 0-1 knapsack
    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';
}

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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27