제출 #1192265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192265		NAMIN	Long Distance Coach (JOI17_coach)	C++20	100 / 100	138 ms	18004 KiB

coach

#include <bits/stdc++.h>

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

using namespace std;

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

struct Line{
	ll m,p;
};

ll len = 1; // lenght of leechaotree

struct leechaotree{
	vector<Line> tree;
	leechaotree(ll l){
		while(len < l){
			len *= 2;
		}
		tree = vector<Line>(2*len,{0,(ll)1e18});
	}
	
	ll calc(Line line,ll x){// calc mx+p
		return 1LL*(-x+1)*line.m+line.p;
	}

	void insert(Line nw,ll l=0,ll r=len-1,int v=1){
		ll mid = l+(r-l)/2;
		if(calc(nw,mid) < calc(tree[v],mid)){ // nw is better than tree[v]
			swap(tree[v],nw); // remplace tree[v] and continue with it
		}
		if(r==l) // you're in a leaf
			return;
		else if(calc(nw,l) < calc(tree[v],l)){ // intersection at left
			insert(nw,l,mid,v*2);
		}
		else // intersection of nw and tree[v] on the right or non-existent
			insert(nw,mid+1,r,v*2+1);

	}

	ll query(ll x,ll l=0,ll r=len-1,int v=1){ // find best on the path
		if(l==r) // at a leave
			return (-x+1)*tree[v].m+tree[v].p;
		ll mid = l+(r-l)/2;
		if(x <= mid) // x is on the left
			return min((-x+1)*tree[v].m+tree[v].p,query(x,l,mid,v*2));
		else // x is on the right
			return min((-x+1)*tree[v].m+tree[v].p,query(x,mid+1,r,v*2+1));
	}
};

void solve(){
	ll X,N,M,W,T;
	cin >> X >> N >> M >> W >> T;
	
	vector<ll> S(N);
	for(int i=0;i<N;i++)
		cin >> S[i];
	S.push_back(X);
	vector<pass> passager(M);
	for(int i=0;i<M;i++){
		cin >> passager[i].d >> passager[i].c;
	}
	sort(passager.begin(),passager.end());
	sort(S.begin(),S.end(),[&](const ll& a,const ll& b){ return a%T < b%T;});

	vector<ll> pref(M+1,0);
	for(int i=1;i<=M;i++){
		pref[i] = pref[i-1]+passager[i-1].c;
	}

	vector<ll> last(N+1,0); // represent the most left passenger before stop i
	for(int i=0;i<=N;i++){
		pass p = {S[i]%T,-1LL};
		last[i] = upper_bound(passager.begin(),passager.end(),p)-passager.begin()-1;
	}
	
	vector<ll> dp(M+1,1e18);
	dp[M] = 0;
	leechaotree lct(M+1);
	for(int i=M-1,j=N;i>=0;i--){ // i = passengers, j = stops
		while(j >= 0 && i <= last[j]){ // while there's a stop at left of i
			ll Dlst = passager[last[j]].d;
			//line representation :
			//
			// dp[i] = pref[last[j]+1]-pref[i] + ((last[j]-i+1)*((S[j]-Dlst)/T)*W)
			// 		   + dp[i-1]
			// 		 = ( (-i+1) * ((S[j]-Dlst)/T)*W
			// 	  	   + ((S[j]-Dlst)/T)*W+dp[last[j]+1]+pref[last[j]+1] ) - pref[i]
			//
			// dp[i] = m*x+p - pref[i]
			// x = (-i+1)
			// m = ((S[j]-Dlst)/T)*W
			// p = last[j]*((S[j]-Dlst)/T)*W + dp[last[j]+1]+pref[last[j]+1]

			Line line = {((S[j]-Dlst)/T)*W,last[j]*((S[j]-Dlst)/T)*W
										   +dp[last[j]+1]+pref[last[j]+1]};
			lct.insert(line);
			j--;
		}
		ll Di = passager[i].d;
		dp[i] = dp[i+1]+((X-Di)/T+1)*W; // passenger[i] don't leave

		dp[i] = min(dp[i],-pref[i]+lct.query(i)); // passenger[i] leave at perfect
												  // time or don't
	}
	
	cout << dp[0] + ((X/T+1) * W) << endl; // best cost for passengers + driver cost
}

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