Submission #245746

#	Time	Username	Problem	Language	Result	Execution time	Memory
245746		jabeznguyen	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	39 ms	16992 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int (i)=int(a);i<=int (b);i++)
#define ff(i,a,b) for(int (i)=int (a);i<int(b);i++)
#define F(i,a,b) for(int (i)=int (a);i>=int (b);i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
const double eps=1e-5,pi=acos(-1.0);
const int N=1e6+6,inf=1<<30,mod=1e9+7;
ll n,m,k,a,b,c,t;
ll ex[N],ans=0;
priority_queue<int> heap;
int main(){
	cin>>n>>m>>k>>a>>b>>c>>t;
	ff(i,0,m){
		cin>>ex[i];
	}
	if((n-1)*b<=t) ans++;
	ff(i,0,m-1){
		ll iti=(ex[i]-1)*b;
		if(iti>t) continue;
		ll qtq=(t-iti)/a;
		ll range=min(ex[i+1]-1,ex[i]+qtq);
		ans+=range-ex[i]+1;
		if(i==0) ans--;
		for(int j=0;j<k&&range<ex[i+1]-1;j++){
			ll tm=iti+(range-ex[i]+1)*c;
			if(tm>t) continue;
			ll q=(t-tm)/a;
			ll new_range=min(range+1+q,ex[i+1]-1);
			heap.push(new_range-range);
			range=new_range;
		}
	}
	for(int i=m;i<k;i++){
		if(heap.empty()) break;
		ans+=heap.top();
		heap.pop();
	}
	cout<<ans;
}

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