Submission #1161985

#TimeUsernameProblemLanguageResultExecution timeMemory
1161985brover29Semiexpress (JOI17_semiexpress)C++17
100 / 100
3 ms328 KiB
#include <bits/stdc++.h> //qwerty47924692 using namespace std; using ll = long long; const ll N=3005; const string br="617283"; #define sz(a)(ll)a.size() #define f first #define s second ll n,m,k,a,b,c,t,d[N],s[N],L[N],dist[N],u[N]; ll cost(ll i,ll k){ if(i>n)return 0; return min(n-i,(t-k)/a); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k>>a>>b>>c>>t; ll ans=0; for(ll i=1;i<=m;i++)cin>>s[i]; for(ll i=1;i<=m;i++){ if(s[i]>1&&t-(s[i]-1)*b>=0)ans++; dist[i]=(t-(s[i]-1)*b); if(dist[i]<0)continue; ll l=s[i]+dist[i]/a+1,r=s[i+1]; L[i]=min(l,r); } for(ll iter=1;iter<=k-m;iter++){ ll id=-1,mx=0; for(ll i=1;i<m;i++){ if(dist[i]<0)continue; ll cost=t-((s[i]-1)*b+(L[i]-s[i])*c); if(cost<0||L[i]==s[i+1])continue; ll cnt=max(0ll,min(s[i+1]-1-L[i],cost/a))+1; if(cnt>mx){ mx=cnt; id=i; } } if(id==-1)break; ll cost=t-((s[id]-1)*b+(L[id]-s[id])*c); ll cnt=max(0ll,min(s[id+1]-1-L[id],cost/a))+1; L[id]+=cnt; } for(ll i=1;i<m;i++){ if(dist[i]>=0)ans+=max(0ll,L[i]-s[i]-1); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...