Submission #1231728

#TimeUsernameProblemLanguageResultExecution timeMemory
1231728mathmemonistKnapsack (NOI18_knapsack)C++20
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0); #define pb push_back using ll = long long; const int MAXK = 2005; // max weight capacity int main() { fastio int k, n; cin >> k >> n; vector<int> value(n+1), weight(n+1), freq(n+1); for (int i = 1; i <= n; i++) { cin >> value[i] >> weight[i] >> freq[i]; } // Use binary decomposition to convert bounded knapsack to 0/1 knapsack vector<int> new_weight, new_value; for (int i = 1; i <= n; i++) { int f = freq[i], w = weight[i], v = value[i]; for (int j = 1; f > 0; j <<= 1) { int cnt = min(j, f); new_weight.pb(cnt * w); new_value.pb(cnt * v); f -= cnt; } } // Now apply 0/1 knapsack DP on new_weight/new_value vector<int> dp(k + 1, 0); for (int i = 0; i < new_weight.size(); i++) { for (int j = k; j >= new_weight[i]; j--) { dp[j] = max(dp[j], dp[j - new_weight[i]] + new_value[i]); } } cout << dp[k] << endl; 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...