Submission #653887

#	Time	Username	Problem	Language	Result	Execution time	Memory
653887		fahimcp495	Knapsack (NOI18_knapsack)	C++17	100 / 100	69 ms	5104 KiB

knapsack

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

#define dbg(a)  cerr << #a << ": " << a << "\n"

using ll = long long;

void solve() {
  ll s, n;  cin >> s >> n;
  vector<array<ll, 2>> vk[s + 1];
  for (int i = 0; i < n; ++i) {
    ll vi, wi, ki;  cin >> vi >> wi >> ki;
    vk[wi].push_back({vi, ki});
  }

  vector<array<ll, 2>> a;
  for (int w = 1; w <= s; ++w) {
    sort(vk[w].rbegin(), vk[w].rend());
    int left = s / w;
    for (auto [v, k]: vk[w]) {
      while (left > 0 and k > 0) {
        a.push_back({w, v});
        left--, k--;
      }
    }
  }

  vector<ll> dp(s + 1);
  for (auto [w, v]: a) {
    for (ll i = s - w; i >= 0; --i) {
      dp[i + w] = max(dp[i + w], dp[i] + v);
    }
  }

  cout << *max_element(dp.begin(), dp.end()) << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);

  int tc = 1;
  for (int t = 1; t <= tc; ++t) {
    solve();
  }
}

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