Submission #629460

#TimeUsernameProblemLanguageResultExecution timeMemory
629460leeminhduc2Knapsack (NOI18_knapsack)C++17
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define ll long long #define ft first #define sc second using namespace std; const int N=1e5+10; ll s,n,v[N],w[N],k[N],dp[N]; void lulu_solution() { cin >> s >> n; for (ll i=1;i<=n;i++) { cin >> v[i] >> w[i] >> k[i]; for (ll st=0;st<w[i];st++){ deque<pair<ll,ll>> dq; for (ll j=st;j<=s;j+=w[i]) { ll prev=dp[j]-((j-st)/w[i])*v[i]; while (dq.size()&&(j-dq.front().ft)/w[i]>k[i]) dq.pop_front(); while (dq.size()&&dq.back().sc<prev) dq.pop_back(); dq.push_back({j,prev}); if (j!=st) { dp[j]=max(dp[j],((j-st)/w[i])*v[i]+dq.front().sc); } } } } cout << *max_element(dp,dp+s); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); lulu_solution(); }
#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...