P11650 [COCI 2024/2025 #4] 力 / Benzinska

题目背景

译自 COCI 2024/2025 #4 T2。$\texttt{1s,0.5G}$。满分为 $70$。

题目描述

在数轴上，Malnar 从原点（$x=0$）出发，前往 $x=X$ 处。

Malnar 初始有 $D$ 单位能量，每走一个单位长度消耗一单位能量。在整个过程中，能量必须不小于 $0$。

有 $n$ 个餐馆，第 $i$ 个餐馆位于 $x=x_i$ 处，在第 $i$ 个餐馆用餐可以使能量增加 $y_i$。至多只能在每个餐馆用一次餐，且不同餐馆的 $x_i$ 可能相同。

求出为了达成目标，至少需要在多少个餐馆用餐。

输入格式

第一行，三个正整数 $n,D,X$。

第二行，$n$ 个正整数 $x_1,\ldots,x_n$。

第三行，$n$ 个正整数 $y_1,\ldots,y_n$。

输出格式

如果不可能，输出一行一个 $\texttt{-1}$。

否则输出一行一个非负整数表示答案。

输入输出样例 #1

输入 #1

5 5 12
3 4 7 8 11
3 2 1 2 1

输出 #1

3

输入输出样例 #2

输入 #2

5 10 40
1 20 30 2 38
7 7 7 7 7

输出 #2

5

输入输出样例 #3

输入 #3

4 5 12
3 6 9 10
2 1 2 2

输出 #3

-1

说明/提示

样例解释

样例 $1$ 解释：在第 $1,2,4$ 个餐馆用餐。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• $1\le D,X,y_i\le 10^9$；
• $1\le x_i\lt X$。

子任务编号	$n\le$	特殊性质	得分
$1$	$2\times 10^5$	A	$15$
$2$	$10^3$		$30$
$3$	$2\times 10^5$		$25$

• 特殊性质 A：$y_i$ 全相等。

#5719. 「COCI 2024/2025 #4」Benzinska

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #4 T2「Benzinska」

Čakovec 的训练营已经开始了，但 Mr. Malnar 还在流连于 Zagreb 的餐厅。为了消耗掉摄入的热量，他决定骑自行车前往 Čakovec。

Mr. Malnar 从 Zagreb $(x=0)$ 出发，初始能量为 $D$，目标是到达距离 Zagreb $X$ 米远的 Čakovec $(x=X)$。每行驶一米需要消耗一个单位的能量。为了避免昏厥，在旅途中的任何时刻，他的能量值都不能变为负数。

沿途有 $n$ 家餐馆，第 $i$ 家餐馆位于距离起点 $x_i$ 米处。多个餐馆可能位于同一位置。若 Mr. Malnar 选择在第 $i$ 家餐馆用餐，他的能量将增加 $y_i$。他不能在同一家餐馆多次用餐。请帮他确定为了安全到达 Čakovec，他最少需要在多少家餐馆用餐。

输入格式

第一行包含三个整数 $n, D$ 和 $X$ $(1 \leq n \leq 2 \cdot 10^{5}, 1 \leq D, X \leq 10^{9})$，代表餐馆的数量、初始能量以及城市之间的距离。

第二行包含 $n$ 个整数 $x_i$ $(1 \leq x_i < X)$，代表各餐馆的位置。

第三行包含 $n$ 个整数 $y_i$ $(1 \leq y_i \leq 10^{9})$，代表 Mr. Malnar 在每家餐馆用餐所能获得的能量。

输出格式

输出仅一行，包含一个整数，表示 Mr. Malnar 安全到达 Čakovec 所需的最少用餐次数。若无法到达 Čakovec，则输出 $-1$。

样例 1

输入

5 5 12
3 4 7 8 11
3 2 1 2 1

输出

3

在 $x=3$ 时，Mr. Malnar 将剩余 $2$ 单位能量。在第一家餐馆，他将用餐，且他的能量将增加到 $2+3=5$。在 $x=4$ 时，他将剩余 $4$ 单位能量。在第二家餐馆，他将用餐，且他的能量将增加到 $4+2=6$。在 $x=8$ 时，他将剩余 $2$ 单位能量。在第四家餐馆，他将用餐，且他的能量将增加到 $2+2=4$。他总计在三家餐馆用餐。

样例 2

输入

5 10 40
1 20 30 2 38
7 7 7 7 7

输出

5

样例 3

输入

4 5 12
3 6 9 10
2 1 2 2

输出

-1

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$15$	对于所有的 $i, j$，有 $y_i = y_j$
$2$	$30$	$n \leq 1000$
$3$	$25$	无附加限制