← 返回题目列表

Codeforces · 1738/B

B. 前缀和瘾君子

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

假设 $$$a_1, a_2, \dots, a_n$$$ 是长度为 $$$n$$$ 的已排序整数序列,使得 $$$a_1 \leq a_2 \leq \dots \leq a_n$$$。

对于每个 $$$1 \leq i \leq n$$$,前 $$$i$$$ 项 $$$a_1, a_2, \dots, a_i$$$ 的前缀和 $$$s_i$$$ 定义为 $$$$$$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i。 $$$$$$

现在你得到了前缀和的最后 $$$k$$$ 项,它们是 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$。您的任务是确定这是否可行。

正式地,给定 $$$k$$$ 整数 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$,任务是检查是否存在序列 $$$a_1, a_2, \dots, a_n$$$ 使得

1. $$$a_1 \leq a_2 \leq \dots \leq a_n$$$,以及
2. 对于所有 $$$n-k+1 \leq i \leq n$$$,$$$s_i = a_1 + a_2 + \dots + a_i$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq n$$$),分别表示序列 $$$a$$$ 的长度和前缀和的项数。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$ 对于每个 $$$n-k+1 \leq i \leq n$$$)。

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

输出

对于每个测试用例,如果可能,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4

输出 #1

Yes
Yes
No
No

注意

在第一个测试用例中,我们有唯一的序列 $$$a = [1, 1, 1, 1, 1]$$$。

在第二个测试用例中,我们可以选择,例如$$$a = [-3, -2, -1, 0, 1, 2, 3]$$$。

在第三个测试用例中,前缀和定义了唯一的序列 $$$a = [2, 1, 1]$$$,但它没有排序。

在第四个测试用例中,可以证明不存在具有给定前缀和的序列。