제출 #919747

#제출 시각아이디문제언어결과실행 시간메모리
919747imarnKnapsack (NOI18_knapsack)C++14
100 / 100
240 ms8016 KiB
#include<bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define vvi vector<vi> #define vp vector<pii> using namespace std; const int N=1e6+5; ll dp[2][2005]{0}; ll ans[2005]{0}; deque<pll>dq[2005]; vector<pll>g[2005]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int s,n;cin>>s>>n; ll a[n],b[n],c[n]; for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>c[i],g[b[i]].pb({a[i],c[i]}); int cr=0; for(int i=1;i<=s;i++){ sort(g[i].begin(),g[i].end(),greater<pll>()); int t = s/i;int tt=0; for(auto it : g[i]){ tt+=it.s; a[cr]=it.f,b[cr]=i,c[cr]=it.s;cr++; if(tt>=t)break; } }n=cr; int nw=0,pr=0; for(int i=0;i<n;i++){ pr=nw;nw=1-nw; for(int j=b[i];j<=s;j++){int id=(j)/b[i]; dp[nw][j]=dp[pr][j]; while(!dq[j%b[i]].empty()&&dq[j%b[i]].back().f+min(id-dq[j%b[i]].back().s+1,c[i])*a[i]<=dp[pr][j-b[i]]+a[i])dq[j%b[i]].pop_back(); while(!dq[j%b[i]].empty()&&id-dq[j%b[i]].front().s+1>=c[i]){ ans[j%b[i]]=max(ans[j%b[i]],dq[j%b[i]].front().f+c[i]*a[i]);dq[j%b[i]].pop_front(); } dq[j%b[i]].pb({dp[pr][j-b[i]],id}); if(!dq[j%b[i]].empty())dp[nw][j]=max(dp[nw][j],dq[j%b[i]].front().f+min(id-dq[j%b[i]].front().s+1,c[i])*a[i]); dp[nw][j]=max(dp[nw][j],ans[j%b[i]]); } for(int j=0;j<b[i];j++)dq[j].clear(),ans[j]=0; }cout<<dp[nw][s]; }
#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...