CF1889B Doremy's Connecting Plan

Doremy 生活在一个由 $n$ 个城市组成的国家，这些城市编号从 $1$ 到 $n$，第 $i$ 个城市有 $a_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 \times 10^5$，$1 \le c \le 10^6$），分别表示节点数和常数 $c$。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^{12}$），表示每个城市的人口。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果可以让图变为连通图，输出 "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 无法添加任何边。 由 ChatGPT 4.1 翻译