Submission #1262657

#TimeUsernameProblemLanguageResultExecution timeMemory
1262657sohamsen15Knapsack (NOI18_knapsack)C++20
73 / 100
1108 ms300484 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.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]; if (n == 1) { cout << (min(c / w[0], k[0]) * v[0]) << "\n"; return 0; } for (int i = 0; i < n; i++) k[i] = min(k[i], 2000ll); ll total = 0; vector<ll> vt, wt; for (ll i = 0; i < n; i++) { ll copy = k[i], currpow = 0; while (copy > 0) { ll next = min((ll) pow(2, currpow), (ll) copy); vt.push_back(v[i] * next); wt.push_back(w[i] * next); copy -= pow(2, currpow); currpow++; total++; } } map<pll, ll> memo; function<ll(ll, ll)> f = [&](ll i, ll j) { if (j < 0) return -9999999999999ll; if (i < 0) return 0ll; if (memo.count({i, j})) return memo[{i, j}]; return memo[{i, j}] = max(vt[i] + f(i - 1, j - wt[i]), f(i - 1, j)); }; cout << f(total - 1, c); }
#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...