Submission #1316097

#TimeUsernameProblemLanguageResultExecution timeMemory
1316097WH8Semiexpress (JOI17_semiexpress)C++17
100 / 100
1 ms332 KiB


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define mt make_tuple
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
#define lol tuple<int,int,int>

signed main(){
	int n,m,k,a,b,c,t;cin>>n>>m>>k>>a>>b>>c>>t;
	vector<int> v(m);
	for(int i=0;i<m;i++)cin>>v[i];
	k=k-m;
	int ans=0;
	priority_queue<lol> pq;
	for(int i=0;i<m-1;i++){
		if((v[i]-1) * b > t)break;
		if((v[i+1]-1) * b <= t){
			ans++;
		}
		int s=(t-(v[i]-1)*b)/a;
		int cur=min(s, v[i+1]-v[i]-1);
		int j=v[i]+cur+1;
		ans+=cur;
		int cand=0;
		if(j < v[i+1]){
			int p=(t-(v[i]-1)*b-c*(j-v[i]));
			//printf("j %lld p %lld\n", j, p);
			if(p < 0)continue;
			cand=min(v[i+1]-j, p/a + 1);
			if(cand) pq.push({cand, j, i});
		}
		//printf("stop at %lld, cur %lld, next %lld\n", v[i], cur, cand);
	}
	//cout<<ans<<endl;
	for(int times=0;times<k;times++){
		if(pq.empty())break;
		auto [plus, pos, i] = pq.top(); pq.pop();
		//printf("placed at %lld to obtain %lld\n", pos, plus);
		ans+=plus;
		pos+=plus;
		if(pos < v[i+1]){
			int p=(t-(v[i]-1)*b-(pos-v[i])*c);
			//printf("wanna place at %lld, p %lld\n", pos, p);
			if(p < 0)continue;
			int cand=min(v[i+1]-pos, p/a + 1);
			//printf("next place at %lld to possibly get %lld\n", pos, cand);
			pq.push({cand, pos, i});
		}
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...