답안 #715703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715703	2023-03-27T14:36:23 Z	valerikk	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2000 ms	14260 KB

coach

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const ll INF = 2e18;

int n, m;
ll X, T, W;
ll s[N];
ll d[N], c[N];
ll cost[N];
ll mn[N];
ll dp[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> X >> n >> m >> W >> T;
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
	}
	sort(s, s + n);
	s[n++] = X;
	{
		vector<pair<ll, ll>> kek(m);
		for (int i = 0; i < m; ++i) {
			cin >> kek[i].first >> kek[i].second;
		}
		sort(kek.begin(), kek.end());
		for (int i = 0; i < m; ++i) {
			d[i] = kek[i].first;
			c[i] = kek[i].second;
		}
	}
	for (int i = 0; i < m; ++i) {
		cost[i] = ((X - d[i]) / T + 1) * W;
	}
	for (int i = 0; i < m; ++i) {
		mn[i] = INF;
	}
	for (int i = 0; i < n; ++i) {
		int ind = lower_bound(d, d + m, s[i] % T) - d - 1;
		if (ind != -1) {
			mn[ind] = min(mn[ind], s[i] / T * W);
		}
	}
	for (int i = 0; i < m; ++i) {
		dp[i + 1] = dp[i] + cost[i];
		for (int j = 0; j <= i; ++j) {
			cost[j] = min(cost[j], mn[i]);
		}
		ll sum = 0;
		for (int j = i; j >= 0; --j) {
			sum += cost[j] + c[j];
			dp[i + 1] = min(dp[i + 1], dp[j] + sum);
		}
	}
	cout << dp[m] + (X / T + 1) * W << "\n";
	return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	328 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	1 ms	328 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	328 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	6 ms	524 KB	Output is correct
39	Correct	5 ms	512 KB	Output is correct
40	Correct	5 ms	472 KB	Output is correct
41	Correct	5 ms	468 KB	Output is correct
42	Correct	5 ms	468 KB	Output is correct
43	Correct	5 ms	468 KB	Output is correct
44	Correct	6 ms	468 KB	Output is correct
45	Correct	7 ms	468 KB	Output is correct
46	Correct	6 ms	468 KB	Output is correct
47	Correct	6 ms	468 KB	Output is correct
48	Correct	6 ms	516 KB	Output is correct
49	Correct	5 ms	468 KB	Output is correct
50	Correct	6 ms	468 KB	Output is correct
51	Correct	5 ms	468 KB	Output is correct
52	Execution timed out	2066 ms	14260 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #715703

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