Submission #1184873

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

coach

#include <bits/stdc++.h>

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

using namespace std;

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

ll N,M,X,T,W;
vector<ll> hub;
vector<passagerType> passager;

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

ll dfs(int idxHub,vector<bool> take){
	if(idxHub >= N+1){
		ll res = 0;
		for(int i=0;i<M;i++){
			if(!take[i])
				res += calcNbX(passager[i].d,X-1)*W;
		}
		res += calcNbX(0,X-1)*W;
		return res;
	}
	

	passagerType cur_hub = {hub[idxHub]%T,-1};
	int end = lower_bound(passager.begin(),passager.end(),cur_hub)
													-passager.begin()-1;
	ll res = dfs(idxHub+1,take);
	ll costLeave = 0;
	for(int i=end;i>=0;i--){
		if(take[i])
			continue;
		take[i] = true;
		costLeave += 1LL*(calcNbX(passager[i].d,hub[idxHub]-1)-1)*W+passager[i].c;
		res = min(res,costLeave+dfs(idxHub+1,take));
	}
	return res;
}

void solve(){
	cin >> X >> N >> M >> W >> T;
	hub.resize(N);
	passager.resize(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;
	}*/
	vector<bool> take(M+1,false);
	ll ans = dfs(0,take);

	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: 16 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29