Submission #1254779

#TimeUsernameProblemLanguageResultExecution timeMemory
1254779orny_nabilaKnapsack (NOI18_knapsack)C++20
73 / 100
1096 ms2632 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int32_t main() { int S, N; cin >> S >> N; vector<int>dp(S+1, 0); vector<int>val(N); vector<int>wt(N); vector<int>k(N); for(int i = 0; i<N; ++i) { cin >> val[i] >> wt[i] >> k[i]; } for(int i = 0; i<N; ++i) { for(int p = 1; k[i]>0; p<<=1) { int power = min(p, k[i]); int weight = power*wt[i]; int value = power*val[i]; for(int j = S; j>=weight; --j) { dp[j] = max(dp[j], dp[j-weight]+value); } k[i]-=power; } } cout << dp[S]; 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...