AdditionalFile3254.zip

P6879 [JOI 2020 Final] 集邮比赛 3 / Collecting Stamps 3

题目描述

给定一个周长为 $L$ 的圆，从一个点出发，有 $N$ 个黑白熊雕像，编号为 $1$ 到 $N$，第 $i$ 个雕像在顺时针 $X_i$ 米处，如果你没有在 $T_i$ 秒内收集到这个黑白熊雕像，那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点，他每一秒可以移动一米，并且他可以顺时针或者逆时针的移动。

JOI 君想问，他最多能收集到多少个黑白熊雕像？

输入格式

第一行两个整数 $N,L$ 代表雕像数和圆的周长。
第二行 $N$ 个整数 $X_i$ 代表每个雕像在顺时针多少米处。
第三行 $N$ 个整数 $T_i$ 代表每个雕像需要在多少秒内拿到。

输出格式

一行一个整数代表答案。

输入输出样例 #1

输入 #1

6 25
3 4 7 17 21 23
11 7 17 10 8 10

输出 #1

4

输入输出样例 #2

输入 #2

5 20
4 5 8 13 17
18 23 15 7 10

输出 #2

5

输入输出样例 #3

输入 #3

4 19
3 7 12 14
2 0 5 4

输出 #3

0

输入输出样例 #4

输入 #4

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46

输出 #4

5

说明/提示

样例 1 解释

JOI 君可以按照如下策略拿到 $4$ 个黑白熊雕像：

方向	路程	总时间	第几个雕像	能否拿到
逆时针	$2$ 米	$2$ 秒	$6$	$\sqrt{}$
		$4$ 秒	$5$
顺时针	$7$ 米	$11$ 秒	$1$
	$1$ 米	$12$ 秒	$2$	$\times$
	$3$ 米	$15$ 秒	$3$	$\sqrt{}$

样例 2 解释

JOI 君可以直接一直逆时针走。

样例 3 解释

JOI 君无法得到任何一个雕像。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N \le 12$，$L \le 200$，$X_i \le 200$。
• Subtask 2（10 pts）：$N \le 15$。
• Subtask 3（10 pts）：$L \le 200$，$T_i \le 200$。
• Subtaks 4（75 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $1 \le N \le 200$。
• $2 \le L \le 10^9$。
• $1 \le X_i<L$。
• $X_i < X_{i+1}$。
• $0 \le T_i \le 10^9$。

说明

翻译自 第19回日本情報オリンピック　本選 C スタンプラリー 3。

#3254. 「JOI 2020 Final」邮戳拉力赛 3

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 JOI 2020 Final T3「スタンプラリー 3 / Collecting Stamps 3」。

JOI 君生活的 IOI 国有一个著名的湖泊，今天一场集邮大会在湖边举行。

绕湖一圈总共有 $N$ 种邮票可以收集，编号分别为 $1\ldots N$，收集点绕湖顺时针排列。湖的周长为 $L$，第 $i$ 张邮票 $(1\le i\le N)$ 的收集点在距离出发点顺时针走 $X_i$ 米的位置。

参赛者在比赛开始的时候要站在出发点的位置，当大会开始时，参赛者可以绕湖顺时针或者逆时针移动，参赛者能够得到第 $i$ 张邮票 $(1\le i\le N)$ 当且仅当他到达收集点的时间在比赛开始时的 $T_i$ 秒以内（含）。

JOI 君也是集邮大会的参与者。他的移动速度是每秒钟 $1$ 米，你可以认为只有移动才会消耗时间。

请你计算他最多能收集到多少种邮票。

输入格式

第一行两个正整数 $N, L$，表示邮票种类和湖泊周长。

接下来一行 $N$ 个数，分别为 $X_1, X_2, \dots, X_N$，表示各种类邮票的收集位置。

接下来一行 $N$ 个数，分别为 $T_1, T_2, \dots, T_N$，表示各种类邮票的最晚可收集时间。

输出格式

输出一行一个整数，表示最多能收集到多少种种类的邮票。

样例 1

输入

6 25
3 4 7 17 21 23
11 7 17 10 8 10

输出

4

JOI 君可以通过下述策略收集到 $4$ 种邮票：

1. 逆时针走 $2$ 米，此时只过了 $2$ 秒，可以收集到第 $6$ 种邮票。
2. 逆时针走 $2$ 米，此时只过了 $4$ 秒，可以收集到第 $5$ 种邮票。
3. 顺时针走 $7$ 米，此时只过了 $11$ 秒，可以收集到第 $1$ 种邮票。
4. 顺时针走 $1$ 米，此时已经过了 $12$ 秒，无法收集到第 $2$ 种邮票。
5. 顺时针走 $3$ 米，此时只过了 $15$ 秒，可以收集到第 $3$ 种邮票。

JOI 君没有办法收集到 $5$ 种或更多邮票，所以答案是 $4$。

样例 2

输入

5 20
4 5 8 13 17
18 23 15 7 10

输出

5

样例 3

输入

4 19
3 7 12 14
2 0 5 4

输出

0

样例 4

输入

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46

输出

5

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le N\le 200, 2\le L\le 10^9, 1\le X_i < L, X_i < X_{i+1}, 0\le T_i \le 10^9$。

子任务编号	分值	特殊限制
$1$	$5$	$N\le 12, L\le 200, T_i\le 200$
$2$	$10$	$N\le 15$
$3$	$10$	$L\le 200,T_i\le 200$
$4$	$75$	无