Submission #33292

#	Time	Username	Problem	Language	Result	Execution time	Memory
33292		ngkan146	Semiexpress (JOI17_semiexpress)	C++98	100 / 100	0 ms	2200 KiB

semiexpress

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k;
ll s[3005];
ll T, A, B ,C;
typedef pair<ll,ll> ii;
#define fi first
#define se second
struct cmpp{
	bool operator () (ii a,ii b){
		// fi = time left
		// b = station left
		ll val1 = min(a.fi / A + 1, a.se);
		ll val2 = min(b.fi / A + 1, b.se);
		
		if (val1 == val2) return a.fi < b.fi;
		
		return val1 < val2;
	}
};
priority_queue <ii,vector<ii>,cmpp> pq;
int main(){
	iostream::sync_with_stdio(0);
	cin >> n >> m >> k;
	cin >> A >> B >> C;
	cin >> T;
	for(int i=1;i<=m;i++)	cin >> s[i];
	int ans = 0;
	for(int i=1;i<m;i++){
		if (T < (s[i]-1) * B) break;
		ll time_left = T - (s[i]-1) * B;
		ll station_left = s[i+1] - s[i] - 1;
		
		ll passable_station = min(station_left, time_left / A);
		
		ans += passable_station;
		time_left -= (passable_station+1) * C;
		station_left -= passable_station;
		
		if (time_left >= 0 && station_left)
			pq.push(ii(time_left, station_left));
	}
	
	for(int i=1;i<=m;i++) ans += (T >= (s[i]-1) * B);
	k -= m;
	//cout << ans-1 << endl;
	while(k-- && pq.size()){
		ii u = pq.top();
		pq.pop();
		
		ll time_left = u.fi;
		ll station_left = u.se;
		
		//cout << time_left << ' ' << station_left << endl;
		
		ll passable_station = min(station_left, time_left / A + 1);
		ans += passable_station;
		
		time_left -= passable_station * C;
		
		if (time_left < 0 || passable_station == station_left) continue;

		pq.push(ii(time_left, station_left - passable_station));
		//cout << ans << endl;
	}
	cout << ans - 1;
}

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