Submission #1261639

#TimeUsernameProblemLanguageResultExecution timeMemory
1261639kaloyanKnapsack (NOI18_knapsack)C++20
73 / 100
1092 ms328 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int S, N; void solve() { cin >> S >> N; int price, award, cnt; int dp[S + 1] = {0}; for(int i = 0 ; i < N ; ++i) { cin >> award >> price >> cnt; int p = 1; while(p <= cnt) { cnt -= p; for(int j = S ; j >= price * p ; --j) { dp[j] = max(dp[j], dp[j - price * p] + award * p); } p *= 2; } if(cnt) { for(int j = S ; j >= price * cnt ; --j) { dp[j] = max(dp[j], dp[j - price * cnt] + award * cnt); } } } cout << dp[S] << "\n"; } void fastIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } signed main() { fastIO(); solve(); }
#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...