← 返回题目列表

Codeforces · 1734/D

D. 史莱姆逃脱

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

您正在玩一款名为“史莱姆逃脱”的游戏。游戏发生在数轴上。最初,有 $$$n$$$ 史莱姆。对于所有正整数 $$$i$$$(其中 $$$1 \le i \le n$$$),第 $$$i$$$ 个史莱姆位于位置 $$$i$$$ 并具有生命值 $$$a_i$$$。您正在 $$$k$$$ 位置控制粘液。

有两个逃逸位置位于 $$$0$$$ 和 $$$n+1$$$ 位置。您的目标是通过执行任意数量的游戏动作来到达两个逃生通道中的任何一个。

在一场游戏中,你将史莱姆向左或向右移动一个位置。但是,如果新位置还有另外的史莱姆,你就必须吸收它。当吸收史莱姆时,你的史莱姆的生命值会因吸收的史莱姆的生命值而增加,然后吸收的史莱姆将从游戏中移除。

请注意,某些史莱姆可能会产生负面健康状况,因此吸收此类史莱姆时您的健康状况会降低。

如果你的史莱姆在游戏过程中的任何时刻健康状况为负值,你会立即输掉游戏。

您可以通过执行任意数量的游戏动作达到两次逃脱之一,而不会输掉游戏吗?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 20\,000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个正整数 $$$n$$$, $$$k$$$ ($$$3 \leq n \leq 200\,000$$$, $$$1 \leq k \leq n$$$) — 史莱姆的数量和史莱姆的位置。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - 史莱姆的健康状况。

保证你的史莱姆的生命值是非负的($$$a_k \geq 0$$$),并且所有其他史莱姆的生命值都非零($$$a_i \ne 0$$$ for $$$i \ne k$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,如果可以逃脱而不丢失,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

示例

输入 #1

6
7 4
-1 -2 -3 6 -2 -3 -1
3 1
232 -500 -700
7 4
-1 -2 -4 6 -2 -4 -1
8 4
-100 10 -7 6 -2 -3 6 -10
8 2
-999 0 -2 3 4 5 6 7
7 3
7 3 3 4 2 1 1

输出 #1

YES
YES
NO
YES
NO
YES

注意

在第一个测试用例中,您控制位置 $$$4$$$ 的粘液,生命值 $$$6$$$。逃脱的一种方法是吸收 $$$5$$$、$$$6$$$ 和 $$$7$$$ 位置的史莱姆。你的史莱姆在 $$$8$$$ 位置以 $$$0$$$ 生命值逃脱。

在第二个测试用例中,您在 $$$1$$$ 位置控制了生命值为 $$$232$$$ 的史莱姆。由于你的史莱姆已经位于逃生位置 $$$0$$$ 旁边,因此你可以移动到那里而不吸收任何史莱姆。

在第三个测试用例中,可以证明你的史莱姆在到达两个逃脱中的任何一个之前,健康状况总是为负。

在第四个测试用例中,您控制位置 $$$4$$$ 的粘液,生命值 $$$6$$$。下面描述了可能的获胜步骤:

1、吸收$$$5$$$、$$$6$$$、$$$7$$$位置的史莱姆:吸收生命值$$$-2$$$的史莱姆后,你的生命值变为$$$4$$$;吸收粘液后变为$$$1$$$,生命值$$$-3$$$;吸收粘液后变为$$$7$$$,生命值为$$$6$$$。
2.吸收$$$3$$$和$$$2$$$位置的史莱姆:你的生命值变为$$$7-7+10=10$$$。
3.吸收$$$8$$$位置的粘液:你的生命值变为$$$10-10=0$$$。
4. 在位置 $$$9$$$ 处使用转义符。

由于你的史莱姆始终保持非负生命值,所以你赢了。