← 返回题目列表

Codeforces · 1889/B

B. 多蕾米的转接计划

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

Doremy 生活在一个由 $$$n$$$ 个城市组成的国家,编号从 $$$1$$$ 到 $$$n$$$,$$$a_i$$$ 人居住在第 $$$i$$$ 个城市。它可以建模为具有 $$$n$$$ 节点的无向​​图。

最初,图中没有边。现在 Doremy 想要将图连接起来。

为此,她可以在 $$$i$$$ 和 $$$j$$$ 之间添加一条边,如果

$$$$$$ \sum_{k \in S} a_k \ge i\cdot j \cdot c, $$$$$$

其中 $$$S$$$ 是当前位于 $$$i$$$ 或 $$$j$$$ 的同一连通分量中的所有节点的集合,$$$c$$$ 是给定常量。

Doremy 能让图连通吗?

如果存在从 $$$i$$$ 到 $$$j$$$ 的路径,则两个节点 $$$(i, j)$$$ 位于同一连通分量中。如果图的所有节点都在同一个连通分量中,则该图是连通的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

第一行包含两个整数 $$$n$$$, $$$c$$$ ($$$2\le n\le 2\cdot 10^5$$$, $$$1 \le c \le 10^6$$$) — 节点数和常数。

每个测试用例的第二行包含 $$$ n $$$ 整数 $$$ a_1,a_2,\ldots,a_n $$$ ($$$0 \le a_i \le 10^{12}$$$) — 居住在第 $$$i$$$ 个城市的人数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果可以使图形连接,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

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

示例

输入 #1

7
4 10
0 20 15 10
2 1
1 1
5 1
0 1 0 4 199
5 2
1 1 3 1 1
5 5
5 6 1 10 2
5 1000000
1000000000000 1000000000000 1000000000000 1000000000000 1000000000000
3 1
0 0 2

输出 #1

Yes
Yes
Yes
No
No
Yes
No

注意

在第一个测试用例中,Doremy 可以按以下顺序添加边:

1. 添加$$$(1,2)$$$。此操作有效,因为 $$$a_1 + a_2 = 20 \ge i\cdot j \cdot c = 20$$$。
2. 添加 $$$(1,3)$$$。此操作有效,因为 $$$a_1 + a_2 + a_3 = 35 \ge i \cdot j \cdot c = 30$$$。
3. 添加$$$(1,4)$$$。此操作有效,因为 $$$a_1 + a_2 + a_3 + a_4 = 45 \ge i \cdot j \cdot c = 40$$$。

在第二个测试用例中,Doremy 可以添加边 $$$(1,2)$$$,因为 $$$a_1 + a_2 =2 \ge 1 \cdot 2 \cdot 1$$$。之后,图形就连接起来了。

在第三个测试用例中,Doremy 可以按 $$$(5,4)$$$、$$$(5,3)$$$、$$$(5,2)$$$ 和 $$$(5,1)$$$ 的顺序添加边。

在第四个测试用例中,Doremy 根本无法添加任何边缘。