Submission #105837

#	Time	Username	Problem	Language	Result	Execution time	Memory
105837		Pro_ktmr	Long Distance Coach (JOI17_coach)	C++14	16 / 100	3 ms	384 KiB

coach

#include"bits/stdc++.h"
using namespace std;
#define int long long
#define MP make_pair
#define PB push_back

int X,N,M,W,T,S[200005],D[200005],C[200005];
vector<pair<int,int> > v;

int solve(int now, int state){
	if(now == M){
		int skip[9];
		for(int i=0; i<M; i++) skip[i] = LLONG_MAX;
		for(int i=0; i<N; i++){
			int start = lower_bound(D, D+M, S[i+1]%T) - D;
			if(start == M) start = 0;
			int idx = (M+start-1)%M;
			for(int j=0; j<M; j++){
				if((state>>idx)%2 == 0) break;
				int now = (S[i+1]-D[idx])/T*T+D[idx];
				//if(now <= S[i]) break;
				skip[idx] = min(skip[idx], now);
				idx = (M+idx-1)%M;
			}
		}
		
		int ans = 0;
		for(int i=0; i<M; i++){
			//cout << skip[i] << endl;
			if(skip[i] == LLONG_MAX){
				ans += ((X-D[i]-1)/T+1)*W;
			}
			else{
				ans += C[i] + ( (skip[i]-D[i])/T )*W;
			}
		}
		//for(int i=0; i<M; i++) cout << (state>>i)%2;
		//cout << endl << ans << endl;
		return ans;
	}
	return min(solve(now+1, state), solve(now+1, state+(1<<now)));
}

signed main(){
	cin >> X >> N >> M >> W >> T;
	if(N > 8 || M > 8) return -1;
	S[0] = -1;
	for(int i=0; i<N; i++) cin >> S[i+1];
	S[N+1] = X;
	N++;
	for(int i=0; i<M; i++){
		int D,C;
		cin >> D >> C;
		v.PB(MP(D,C));
	}
	v.PB(MP(0, -1));
	M++;
	sort(v.begin(), v.end());
	for(int i=0; i<M; i++){
		D[i] = v[i].first;
		C[i] = v[i].second;
	}
	
	//
	
	cout << solve(1,0) << endl;
	
	return 0;
}

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