← 返回题目列表

Codeforces · 1200/B

B. 方块冒险

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

Gildong 正在玩一款名为“方块冒险”的视频游戏。在《方块冒险》中,一行中有 $$$n$$$ 列方块,列编号从 $$$1$$$ 到 $$$n$$$。所有块都具有相同的高度。第 $$$i$$$ 列的高度表示为 $$$h_i$$$,即第 $$$i$$$ 列中堆叠的块数。

Gildong 作为一个只能站在柱子顶部的角色来玩游戏。一开始,角色站在 $$$1$$$-st 列的顶部。游戏的目标是将角色移动到第 $$$n$$$ 列的顶部。

该角色还有一个可以容纳无限多个方块的袋子。当角色位于第 $$$i$$$ 列的顶部时,Gildong 可以根据需要多次执行以下三个操作之一:

- 如果该列上至少有一个方块,则从第$$$i$$$列的顶部移除一个方块并将其放入袋子中;
- 如果袋子里至少有一个方块,则从袋子里取出一个方块并将其放在第 $$$i$$$ 列的顶部;
- 如果 $$$i < n$$$ 且 $$$|h_i - h_{i+1}| \le k$$$,将字符移动到 $$$i+1$$$-st 列的顶部。 $$$k$$$ 是游戏开始时给出的非负整数。请注意,只能移动到下一列。

在前两种类型的动作中,角色保留在第 $$$i$$$ 列中,并且值 $$$h_i$$$ 发生变化。

角色的包里最初有 $$$m$$$ 块。吉尔东想知道是否有可能赢得比赛。帮助吉尔东找到问题的答案。

输入

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le 10^6$$$, $$$0 \le k \le 10^6$$$) — 游戏中的列数、游戏中的块数字符的包开头,以及语句中描述的非负整数$$$k$$$。

每个测试用例的第二行包含 $$$n$$$ 整数。第 $$$i$$$ 整数是 $$$h_i$$$ ($$$0 \le h_i \le 10^6$$$),即第 $$$i$$$ 列的初始高度。

输出

对于每个测试用例,如果有可能赢得比赛,则打印“YES”。否则,打印“NO”。

您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99

输出 #1

YES
NO
YES
NO
YES

注意

在第一种情况下,Gildong 可以从 $$$1$$$-st 列中取出一个块,移动到 $$$2$$$-nd 列,将块放在 $$$2$$$-nd 列上,然后移动到 $$$3$$$-rd 列。

在第二种情况下,Gildong 必须将块放在 $$$1$$$-st 列的包中才能到达 $$$2$$$-nd 列。但不可能到达 $$$3$$$-rd 列,因为 $$$|h_2 - h_3| = 3 > k$$$ 并且无法缩小差距。

在第五种情况下,角色从一开始就已经位于第 $$$n$$$ 列,因此游戏立即获胜。