Submission #1183303

#TimeUsernameProblemLanguageResultExecution timeMemory
1183303dirtycodeheheKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms2628 KiB
#include<bits/stdc++.h> using namespace std; #define int long long signed main(){ int w, n; cin >> w >> n; vector<int> a(n+1, 0); vector<int> v(n+1, 0); vector<int> k(n+1, 0); for(int i = 1; i <= n; ++i){ cin >> v[i] >> a[i] >> k[i]; } vector<int> dp(w+1, 0); for(int i = 1; i <= n; ++i){ int tem = k[i]; for(int h = 1; tem > 0; h <<= 1){ int cnt = min(h, tem); int weight = cnt * a[i]; int value = cnt * v[i]; for(int j = w; j >= weight; --j){ dp[j] = max(dp[j], dp[j - weight] + value); } tem -= cnt; } } cout << dp[w]; }
#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...