Submission #918319

#TimeUsernameProblemLanguageResultExecution timeMemory
918319kotnidKnapsack (NOI18_knapsack)C++14
73 / 100
1032 ms460 KiB
/* knapsack with multiple amount -> express as 2^0, 2^1,.... */ #include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0); cin.tie(0); ll s, n; cin >> s >> n; ll dp[s+1]; memset(dp,0,sizeof dp); for(int i=0; i<n; i++){ ll v, w, k; cin >> v >> w >> k; ll c = 1; while(c <= k && c <= s){ ll v2 = v*c, w2 = w*c; for(int j=s; j>=w2; j--)dp[j] = max(dp[j], dp[j-w2]+v2); k -= c; c *= 2; } if(k != 0){ ll v2 = v*k, w2 = w*k; for(int j=s; j>=w2; j--)dp[j] = max(dp[j], dp[j-w2]+v2); } } cout << dp[s]; }
#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...