Submission #1203590

#TimeUsernameProblemLanguageResultExecution timeMemory
1203590timeflewKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms512 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define all(x) x.begin(), x.end() const int mxS=2e3; ll dp[mxS+1]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int s, n; cin>>s>>n; for(int i=0; i<n; i++) { ll v, w, K; cin>>v>>w>>K;//value weight count for(int r=0; r<w; r++) { deque<pair<ll, ll>> dq; for(int k=r, c=0; k<=s; k+=w, c++) { ll val=dp[k]-1ll*c*v; while(dq.size()&&c-dq.front().ss>K) { dq.pop_front(); } while(dq.size()&&val>=dq.back().ff) { dq.pop_back(); } dq.push_back({val, c}); dp[k]=dq.front().ff+1ll*c*v; } } } 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...