Submission #915839

#	Time	Username	Problem	Language	Result	Execution time	Memory
915839		dsyz	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	460 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (3005)
ll N, A; //normal train has N stations (at pos 1 to N), takes A minutes to move from i to i+1
ll M, B; //express train has M stations (at all positions in express[M]), takes B minutes to move from i to i+1
ll K, C; //semi-express train has K stations, takes C minutes to move from i to i+1
ll T;
ll express[MAXN];
priority_queue<pair<ll,ll> > pq;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>M>>K>>A>>B>>C>>T;
	for(ll i = 0;i < M;i++){
		cin>>express[i];
	}
	ll sum = 0;
	if(B * (N - 1) <= T) sum = 0;
	else sum = -1;
	ll P[M - 1];
	for(ll i = 0;i < M - 1;i++){
		if(B * (express[i]-1) > T){
			continue;
		}
		ll u = min(express[i + 1] - 1,express[i] + (T - B * (express[i]-1)) / A);
        sum += (u - express[i] + 1);
        P[i] = u + 1;
        if(P[i] < express[i + 1] && B * (express[i] - 1) + C * (P[i]-express[i]) <= T){
            pq.push({min(express[i + 1] - 1, P[i] + (T - B * (express[i]-1) - C * (P[i]-express[i])) / A) - P[i] + 1, i});
		}
	}
	for(ll i = 0;i < K - M;i++){
		if(pq.empty()){
			break;
		}
        ll v = pq.top().first;
        ll ind = pq.top().second;
        pq.pop();
        sum += v;
        P[ind] += v;
        if(P[ind] < express[ind + 1] && B * (express[ind]-1) + C * (P[ind]-express[ind]) <= T){
            pq.push({min(express[ind + 1] - 1, P[ind] + (T - B * (express[ind] - 1) - C * (P[ind]-express[ind])) / A) - P[ind] + 1, ind});
		}
	}
	cout<<sum<<'\n';
}

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