제출 #1262658

#제출 시각아이디문제언어결과실행 시간메모리
1262658sohamsen15Knapsack (NOI18_knapsack)C++20
73 / 100
1094 ms18548 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll c, n; cin >> c >> n; vector<ll> v(n), w(n), k(n); for (int i = 0; i < n; i++) cin >> v[i] >> w[i] >> k[i]; // cap multiplicities at 2000 (as in your code) for (int i = 0; i < n; i++) k[i] = min(k[i], 2000ll); vector<ll> vt, wt; for (int i = 0; i < n; i++) { ll copy = k[i], currpow = 1; while (copy > 0) { ll take = min(currpow, copy); vt.push_back(v[i] * take); wt.push_back(w[i] * take); copy -= take; currpow <<= 1; } } vector<ll> dp(c + 1, 0); for (size_t i = 0; i < vt.size(); i++) { for (ll cap = c; cap >= wt[i]; cap--) { dp[cap] = max(dp[cap], dp[cap - wt[i]] + vt[i]); } } cout << dp[c] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...