Submission #854621

#	Time	Username	Problem	Language	Result	Execution time	Memory
854621		willychan	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	0 ms	348 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds




int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m,k;cin>>n>>m>>k;
	k-=m;
	int a,b,c;cin>>a>>b>>c;
	int T;cin>>T;
	vector<ll> stop(m);
	for(int i=0;i<m;i++){
		cin>>stop[i];
		stop[i]--;
	}
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll ans = n;
	for(int i=1;i<m;i++){
		ll st = stop[i-1]*b;
		ll dif = T-st;
		pair<ll,ll> d;
		d = {stop[i-1]+(dif/a)+1,stop[i]};
		if(dif<=0) d = {stop[i-1],stop[i]};
		if(d.second>d.first){
			ans-=d.second-d.first;
			pq.push(d);
		}
	}
	if((n-1)*b>T) ans--;
	for(int i=0;i<k;i++){
		while(pq.size() && pq.top().first>=pq.top().second) pq.pop();
		if(!pq.size()) break;
		pair<ll,ll> d = pq.top();
		//cout<<d.first<<" "<<d.second<<"\n"n;
		pq.pop();
		ll tt = d.first*c;
		if(tt>T){k++;continue;}
		pair<ll,ll> nd = {d.first+((T-tt)/a)+1,d.second};
		if(nd.first>=d.second) ans+=d.second-d.first;
		else{
			ans+=nd.first-d.first;
			pq.push(nd);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 52