답안 #530717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530717	2022-02-26T14:48:09 Z	fhvirus	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2000 ms	10104 KB

coach

#include <bits/stdc++.h>
using namespace std;

const int kN = 200'002;
int N, M;
int64_t X, W, T;
pair<int64_t, int64_t> refill[kN];
pair<int64_t, int64_t> passenger[kN];

int64_t preC[kN];
int prev_passenger[kN];

int64_t dp[kN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> X >> N >> M >> W >> T;
	for (int i = 0; i < N; ++i) {
		int64_t S; cin >> S;
		refill[i].first = S % T;
		refill[i].second = S / T;
	}
	for (int i = 0; i < M; ++i) {
		cin >> passenger[i].first;
		cin >> passenger[i].second;
	}

	refill[N] = pair<int64_t, int64_t>(X % T, X / T);
	sort(refill, refill + N + 1);
	sort(passenger, passenger + M);
	for (int i = 0; i <= N; ++i)
		prev_passenger[i] = lower_bound(passenger, passenger + M, refill[i]) - passenger - 1;
	for (int i = 0; i < M; ++i)
		preC[i + 1] = preC[i] + passenger[i].second;

	for (int i = M - 1; i >= 0; --i) {
		dp[i] = dp[i + 1] + W * (X / T + (passenger[i].first % T < X % T));
		for (int j = N; j >= 0; --j) {
			int r = prev_passenger[j];
			if (r < i) break;
			int64_t val = (preC[r + 1] - preC[i]) + W * (r - i + 1) * (refill[j].second) + dp[r + 1];
			dp[i] = min(dp[i], val);
		}
	}

	cout << dp[0] + W * (X / T + 1) << '\n';
	return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	0 ms	312 KB	Output is correct
28	Correct	0 ms	332 KB	Output is correct
29	Correct	1 ms	316 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	320 KB	Output is correct
34	Correct	0 ms	332 KB	Output is correct
35	Correct	0 ms	332 KB	Output is correct
36	Correct	1 ms	320 KB	Output is correct
37	Correct	0 ms	332 KB	Output is correct

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	0 ms	312 KB	Output is correct
28	Correct	0 ms	332 KB	Output is correct
29	Correct	1 ms	316 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	320 KB	Output is correct
34	Correct	0 ms	332 KB	Output is correct
35	Correct	0 ms	332 KB	Output is correct
36	Correct	1 ms	320 KB	Output is correct
37	Correct	0 ms	332 KB	Output is correct
38	Correct	9 ms	460 KB	Output is correct
39	Correct	8 ms	452 KB	Output is correct
40	Correct	8 ms	496 KB	Output is correct
41	Correct	8 ms	460 KB	Output is correct
42	Correct	8 ms	460 KB	Output is correct
43	Correct	7 ms	460 KB	Output is correct
44	Correct	8 ms	448 KB	Output is correct
45	Correct	8 ms	332 KB	Output is correct
46	Correct	8 ms	460 KB	Output is correct
47	Correct	8 ms	388 KB	Output is correct
48	Correct	8 ms	504 KB	Output is correct
49	Correct	8 ms	496 KB	Output is correct
50	Correct	8 ms	460 KB	Output is correct
51	Correct	8 ms	492 KB	Output is correct

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	0 ms	332 KB	Output is correct
6	Correct	0 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	0 ms	332 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	0 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	0 ms	312 KB	Output is correct
28	Correct	0 ms	332 KB	Output is correct
29	Correct	1 ms	316 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	320 KB	Output is correct
34	Correct	0 ms	332 KB	Output is correct
35	Correct	0 ms	332 KB	Output is correct
36	Correct	1 ms	320 KB	Output is correct
37	Correct	0 ms	332 KB	Output is correct
38	Correct	9 ms	460 KB	Output is correct
39	Correct	8 ms	452 KB	Output is correct
40	Correct	8 ms	496 KB	Output is correct
41	Correct	8 ms	460 KB	Output is correct
42	Correct	8 ms	460 KB	Output is correct
43	Correct	7 ms	460 KB	Output is correct
44	Correct	8 ms	448 KB	Output is correct
45	Correct	8 ms	332 KB	Output is correct
46	Correct	8 ms	460 KB	Output is correct
47	Correct	8 ms	388 KB	Output is correct
48	Correct	8 ms	504 KB	Output is correct
49	Correct	8 ms	496 KB	Output is correct
50	Correct	8 ms	460 KB	Output is correct
51	Correct	8 ms	492 KB	Output is correct
52	Execution timed out	2032 ms	10104 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #530717

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 29.0