Submission #1248156

#TimeUsernameProblemLanguageResultExecution timeMemory
1248156mohamedazizKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms2628 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int W, n; cin >> W >> n; vector<int> weight(n), value(n), cnt(n); for(int i = 0; i < n; i++){ cin >> value[i] >> weight[i] >> cnt[i]; } vector<int> dp(W + 1, 0); // Process each item i for(int i = 0; i < n; i++){ int w = weight[i]; int v = value[i]; int c = cnt[i]; // Binary-split the count c for(int k = 1; c > 0; k <<= 1){ int take = min(k, c); int ww = w * take; int vv = v * take; // 0/1 knapsack update for this pseudo-item for(int cap = W; cap >= ww; cap--){ dp[cap] = max(dp[cap], dp[cap - ww] + vv); } c -= take; } } cout << dp[W] << "\n"; return 0; }
#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...