답안 #105837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105837	2019-04-15T10:29:45 Z	Pro_ktmr	Long Distance Coach (JOI17_coach)	C++14	16 / 100	3 ms	384 KB

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.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	372 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	372 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Runtime error	3 ms	256 KB	Execution failed because the return code was nonzero
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	372 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Runtime error	3 ms	256 KB	Execution failed because the return code was nonzero
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	3 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	372 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	3 ms	384 KB	Output is correct
21	Correct	3 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Runtime error	3 ms	256 KB	Execution failed because the return code was nonzero
24	Halted	0 ms	0 KB	-

답안 #105837

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 0 / 30.0

Subtask #3 0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
0 / 30.0

Subtask #3
0 / 25.0

Subtask #4
0 / 29.0