Submission #899603

#	Time	Username	Problem	Language	Result	Execution time	Memory
899603		dsyz	Semiexpress (JOI17_semiexpress)	C++17	0 / 100	0 ms	344 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<pair<ll,ll>,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;
	for(ll i = 0;i < M - 1;i++){
		sum += max(0ll,min(express[i + 1] - express[i],(T-(i*B))/A));
		if((T-(i*B)-C) >= 0 && ((T-(i*B))/A) + 1 < (express[i + 1] - express[i])){
			pq.push({{min(express[i] + ((T-(i*B))/A)+1 + (T-(i*B)-C)/A,express[i + 1]) - (express[i] + ((T-(i*B))/A) + 1),T-(i*B)-C},{min(express[i] + (T-(i*B)-C),express[i + 1]),i + 1}});
		}
	}
	for(ll i = 0;i < K - M;i++){
		if(pq.empty()){
			sum++;
			continue;
		}
		sum += pq.top().first.first;
		ll used = pq.top().first.second;
		ll done = pq.top().second.first;
		ll limit = pq.top().second.second;
		pq.pop();
		if(used >= C && done + 1 < (express[limit] - express[limit - 1])){
			pq.push({{min(done + 1 + (used-C)/A,express[limit]) - done,used-C},{min(done + 1 + (used-C)/A,express[limit]),i + 1}});
		}
	}
	cout<<sum<<'\n';
}

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