Submission #1260554

#TimeUsernameProblemLanguageResultExecution timeMemory
1260554Mer123haba456Knapsack (NOI18_knapsack)C++20
73 / 100
1094 ms448 KiB
#include <bits/stdc++.h> using namespace std; #define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define N lli(2e5) #define MOD lli(1e9 + 7) #define heps(v) v.begin(), v.end() typedef long long int lli; typedef vector<lli> vlli; typedef pair<lli, lli> plli; typedef vector<plli> vplli; typedef pair<lli, plli> pplli; typedef vector<pplli> vpplli; lli n,m,k,q,t; vlli vect; lli dp[N]; int main() { fast_io cin >> m >> n; for(lli i = 0;i<n;i++){ cin >> q >> t >> k; for(lli j = 0;j<=29;j++){ lli su = 1<<j; if(k >= su){ k-=su; lli suag = su * t; lli sudeg = su * q; for(lli z = m - suag;z>=0;z--){ if(z == 0){ dp[z + suag] = max(dp[z+suag], sudeg); continue; } if(dp[z] <= 0) continue; dp[z + suag] = max(dp[z + suag], dp[z] + sudeg); } }else break; } if(k > 0){ lli suag = k * t; lli sudeg = k * q; for(lli z = m - suag;z>=0;z--){ if(z == 0){ dp[z + suag] = max(dp[z+suag], sudeg); continue; } if(dp[z] <= 0) continue; dp[z + suag] = max(dp[z + suag], dp[z] + sudeg); } } } lli cev = 0; for(lli i = 0;i<=m;i++){ cev = max(cev, dp[i]); } cout << cev << 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...