Submission #1175546

#TimeUsernameProblemLanguageResultExecution timeMemory
1175546zaki98Knapsack (NOI18_knapsack)C++20
73 / 100
1096 ms18620 KiB
#include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int s, n; cin >> s >> n; vector<int> v(n), w(n), k(n); for(int i=0; i<n; i++){ cin >> v[i] >> w[i] >> k[i]; k[i]= min(s/w[i]+1, k[i]); } vector<int> weight, value; for(int i=0; i<n; i++){ int opt = k[i]; for(int x =1; x<=opt; x<<=1) { value.push_back(x*v[i]); weight.push_back(x*w[i]); opt -= x; } if(opt>0) { value.push_back(opt*v[i]); weight.push_back(opt*w[i]); } } vector<int> dp(2e3+10, 0); for(int i=0; i<value.size(); i++){ for(int j =s+10; j>=weight[i]; j--){ dp[j]= max(dp[j], dp[j-weight[i]]+value[i]); } } cout << dp[s]<< endl; }
#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...