← 返回题目列表

AtCoder · maximum_cup_2018_d

D. 许多人转来转去

中文机器翻译题面 查看原题

配点 : 100 点

問題文

有一天,S决定沿着环路行驶。

这条环路上每隔一段距离就有休息区。 它们的编号最大为0 减去 M - 1 到的编号被标记。
你 从休息区0开始,0 → 1 → 2 → … → (M - 2) → (M - 1) → 0 → 1 → 2 → … 然后四处走走。

S 你的车有燃料1休息区升1您可以前进一步。
但加注燃油时,提前准备的加注量为 来自 a_1 , a_2 , a_3 ,…, a_{N-1} , a_{N} 是 N 油箱 1 您必须选择并补充一个或多个。
加油后油箱变空,因此如果您使用相同的油箱, 您选择的次数不能超过2次。 汽车一旦开始行驶,直到耗尽燃料才会停下来,所以如果你想在某个休息站停下来,你就必须选择一个油箱来加满油,以免那里的燃料耗尽。

S 你是号码 我在L的休息站与朋友会面,我的车没油了。0,选择多个油箱,重新加注,然后输入数量 从0和数字的剩余区域开始 我想停在L休息区。
但是环路X如果开车超过30分钟,将违反本市交通法规。

你X圈数 确定是否有办法选择允许您在L中的休息站停车的油箱。

补充燃油是第一步。 仅1次。另外,开始后立即1再次定义轮数和数量 当您到达0处的休息区时,下一圈将开始。

制約

  • 1 \leq N \leq 10000
  • 3 \leq M \leq 1000
  • 1 \leq L \leq M - 1
  • 2 \leq X \leq 10000
  • 1 \leq a_i \leq 10000

入力

输入是按以下格式从标准输入给出的。

N M L X
a_1 a_2 ... a_N

1 行显示油箱数量。 N , 休息区数量 M ,所需休息站的编号 L 及违规圈数 X 。 表示

2 准备好的 每个 N 油箱的加注量以正整数给出。 指示第a_i 是 您也可以写 i 个水箱的补充量。

出力

你 X 圈数 确定是否有办法选择允许您在 L 中的休息区,则输出Yes,如果不能停,则输出No。


入力例 1

5 11 7 5
1 4 5 8 9

出力例 1

Yes

合并数字 无法创建 7(1 圈)。

1 + 8 + 9 = 18 和1圈数 + 目标数 因为它等于(11+7 = 18) 您可以停在 2 周目(\leq X = 5) 。 无法创建


入力例 2

5 5 3 2
1 4 5 9 12

出力例 2

No

合并数字 无法创建 3(1 周目), 8(2 周)。

1 + 12 = 13 和2 圈数 + 目标数 因为它等于 (10+3) 您可以停在 3 你可以在第一圈停下来,但是X = 2 否,因为它超过了圈数。


入力例 3

5 10 3 100
1 4 7 10 14

出力例 3

No

无论您选择哪种组合 有3(1 周目), 13(2 周目), 23(3 周目), 33(4 圈)。