Submission #161381

#	Time	Username	Problem	Language	Result	Execution time	Memory
161381		oolimry	Semiexpress (JOI17_semiexpress)	C++14	18 / 100	2 ms	504 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	long long n, m, k;
	cin >> n >> m >> k;
	long long a, b, c, t;
	cin >> a >> b >> c >> t;
	
	long long ans = 0;
	
	long long pos[m];
	long long dist[m];
	for(int i = 0;i < m;i++){
		cin >> pos[i];
		dist[i] = (pos[i] - 1) * b;
	}
	
	typedef pair<long long,long long> ii;
	queue<ii> options[m];
	if(dist[m-1] <= t) ans++;
	for(int i = 0;i < m-1;i++){
		if(dist[i] > t){
			continue;
		}
		long long l = pos[i];
		long long predist = dist[i];
		/*
		ans += (t - dist[i]) / a;
		if(i != 0) ans++;
		
		l += ((t - dist[i]) / a) + 1;
		*/
		bool has = false;
		
		while(true){
			//cout << l << "\n";
			if(predist > t) break;
			if(l == pos[i+1]) break;
			long long nl = l + ((t - predist) / a) + 1;
			
			if(nl >= pos[i+1]){
				nl = pos[i+1];
			}
			if(has){
				options[i].push(ii(nl-l, i));
				if(options[i].size() > 3000) break;
				//cout << nl-l << " " << i << "\n";
			}
			else{
				has = true;
				ans += (nl-l);
			}
			predist += (nl-l)*c;
			l = nl;
			
		}
		//cout << "\n";
	}
	
	
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	for(int i = 0;i < m;i++){
		if(!options[i].empty()){
			pq.push(options[i].front());
			options[i].pop();
		}
	}
	
	for(int i = 0;i < k-m;i++){
		if(pq.empty()) break;
		ii x = pq.top();
		ans += x.first;
		pq.pop();
		if(!options[x.second].empty()){
			pq.push(options[x.second].front());
			options[x.second].pop();
		}
	}
	///for the 1st station
	ans--;
	cout << ans;
	
	
	
	
}

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