Submission #1316406

#TimeUsernameProblemLanguageResultExecution timeMemory
1316406boclobanchatSemiexpress (JOI17_semiexpress)C++20
100 / 100
1 ms332 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005;
long long pos[MAXN],F[MAXN],cap[MAXN];
priority_queue< pair<long long,int> > pq;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n,m,k,a,b,c,t,ans=0;
	cin>>n>>m>>k>>a>>b>>c>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>pos[i];
		if(i>1) ans+=((pos[i]-1)*b<=t);
	}
	for(int i=2;i<=m;i++)
	{
		cap[i]=pos[i]-pos[i-1]-1,F[i]=max(0LL,min(cap[i],(t-(pos[i-1]-1)*b)/a));
		ans+=F[i];
		if(t-(pos[i-1]-1)*b-(F[i]+1)*c>=0) pq.push({max(0LL,min(cap[i]-F[i],(t-(pos[i-1]-1)*b-(F[i]+1)*c)/a+1)),i});
	}
	k-=m;
	while(k--&&!pq.empty())
	{
		long long x=pq.top().first,y=pq.top().second;
		pq.pop(),ans+=x;
		F[y]+=x;
		if(t-(pos[y-1]-1)*b-(F[y]+1)*c>=0) pq.push({max(0LL,min(cap[y]-F[y],(t-(pos[y-1]-1)*b-(F[y]+1)*c)/a+1)),y});
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...