Submission #1184845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184845		NAMIN	Long Distance Coach (JOI17_coach)	C++20	0 / 100	0 ms	328 KiB

coach

#include <bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;


ll N,M,X,T,W;

struct passagerType{
	ll d,c;
	bool operator<(const passagerType p)const{
		return p.d > d;
	}
};

ll calcNbX(ll D,ll k){
	return (k-D)/T+1;
}

void solve(){
	cin >> X >> N >> M >> W >> T;
	vector<ll> hub(N);
	vector<passagerType> passager(M);
	for(int i=0;i<N;i++)
		cin >> hub[i];
	for(int i=0;i<M;i++)
		cin >> passager[i].d >> passager[i].c;
	
	hub.push_back(X);
	sort(hub.begin(),hub.end());
	sort(passager.begin(),passager.end());
	
	ll ans = 0;
	for(ll h : hub){
		passagerType cur_hub = {h%T,-1};
		int end = lower_bound(passager.begin(),passager.end(),cur_hub)
														-passager.begin()-1;
		ll costLeave=0,costKeep=0,mxDif=0;
		int bestIdx = -1;
		for(int i=end;i>=0;i--){
			costLeave += passager[i].c;
			costKeep += 1LL*(calcNbX(passager[i].d,X-1)-calcNbX(passager[i].d,h-1)+1)*W;
			if(mxDif < costKeep-costLeave){
				bestIdx = i;
				mxDif = costKeep-costLeave;
			}
		}
		vector<passagerType> nextPassager;
		for(int i=0;i<passager.size();i++){
			if(bestIdx != -1 && i >= bestIdx && i <= end){
				ans += 1LL*(calcNbX(passager[i].d,h-1)-1)*W+passager[i].c;
			}
			else
				nextPassager.push_back(passager[i]);
		}
		passager = nextPassager;
	}

	for(int i=0;i<passager.size();i++){
		ans += calcNbX(passager[i].d,X-1)*W;
	}
	ans += calcNbX(0,X-1)*W;

	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29