← 返回题目列表

Codeforces · 1324/E

E. 睡眠时间表

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

Vova 的睡眠时间表非常奇怪。一天有 $$$h$$$ 小时。 Vova 会恰好睡 $$$n$$$ 次。第 $$$i$$$ 次他会在他醒来后的 $$$a_i$$$ 小时后睡觉。您可以假设 Vova 正好在故事的开头醒来(初始时间为 $$$0$$$)。每次 Vova 只睡一天(换句话说,$$$h$$$ 小时)。

Vova 认为,如果他在 $$$l$$$ 和 $$$r$$$ 小时(含)之间开始睡觉,那么第 $$$i$$$ 个睡眠时间就很好。

Vova 可以控制自己,并且在第 $$$i$$$ 次之前可以在两个选项之间进行选择:在 $$$a_i$$$ 小时后或在 $$$a_i - 1$$$ 小时后睡觉。

你的任务是说出如果 Vova 表现最佳,他可以获得的最佳睡眠时间的最大数量。

输入

输入的第一行包含四个整数 $$$n、h、l$$$ 和 $$$r$$$ ($$$1 \le n \le 2000, 3 \le h \le 2000, 0 \le l \le r < h$$$) — Vova 入睡的次数、一天中的小时数以及良好睡眠时间段。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < h$$$),其中 $$$a_i$$$ 是 Vova 第 $$$i$$$ 次进入睡眠状态后的小时数。

输出

打印一个整数——如果 Vova 表现最佳,他可以获得的最大良好睡眠时间。

示例

输入 #1

7 24 21 23
16 17 14 20 20 11 22

输出 #1

3

注意

示例中的最大美好次数为 $$$3$$$。

故事从$$$t=0$$$开始。然后 Vova 在 $$$a_1 - 1$$$ 小时后进入睡眠状态,现在时间是 $$$15$$$。这次不太好。然后 Vova 在 $$$a_2 - 1$$$ 小时后进入睡眠状态,现在时间为 $$$15 + 16 = 7$$$。这一次也不好。然后 Vova 在 $$$a_3$$$ 小时后睡觉,现在时间是 $$$7 + 14 = 21$$$。这次很好。然后 Vova 在 $$$a_4 - 1$$$ 小时后进入睡眠状态,现在时间为 $$$21 + 19 = 16$$$。这次不太好。然后 Vova 在 $$$a_5$$$ 小时后睡觉,现在时间是 $$$16 + 20 = 12$$$。这次不太好。然后 Vova 在 $$$a_6$$$ 小时后睡觉,现在时间是 $$$12 + 11 = 23$$$。这次很好。然后 Vova 在 $$$a_7$$$ 小时后睡觉,现在时间是 $$$23 + 22 = 21$$$。这次也不错。