H B. Prefix Sum Addicts
时间限制2 S
内存限制512 MB
通过率25%(34 / 136)
题目描述
Suppose a1, a2, ..., an is a sorted integer sequence of length n such that a1 <= a2 <= ... <= an.
For every 1 <= i <= n, the prefix sum si of the first i terms a1, a2, ..., ai is defined by
For every 1 <= i <= n, the prefix sum si of the first i terms a1, a2, ..., ai is defined by
Now you are given the last k terms of the prefix sums, which are sn-k+1, ..., sn-1, sn. Your task is to determine whether this is possible.
Formally, given k integers sn-k+1, ..., sn-1, sn, the task is to check whether there is a sequence a1, a2, ..., an such that
- a1 ≤ a2 ≤⋯≤ an, and
- si = a1+ a2+⋯+ai for all n−k+1 ≤ i ≤ n.
输入格式
Each test contains multiple test cases. The first line contains an integer t (1 <= t <= 105) — the number of test cases. The following lines contain the description of each test case.
The first line of each test case contains two integers n (1 <= n <= 105) and k (1 <= k <= n), indicating the length of the sequence a and the number of terms of prefix sums, respectively.
The second line of each test case contains k integers sn-k+1, ..., sn-1, sn (-109 <= si <= 109 for every n-k+1 <= i <= n).
It is guaranteed that the sum of n over all test cases does not exceed 105.
The first line of each test case contains two integers n (1 <= n <= 105) and k (1 <= k <= n), indicating the length of the sequence a and the number of terms of prefix sums, respectively.
The second line of each test case contains k integers sn-k+1, ..., sn-1, sn (-109 <= si <= 109 for every n-k+1 <= i <= n).
It is guaranteed that the sum of n over all test cases does not exceed 105.
输出格式
For each test case, output "Yes" or "No".
输入输出样例
输入复制
4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4
输出复制
Yes
Yes
No
No
数据范围与提示
In the first test case, we have the only sequence a = [1, 1, 1, 1, 1].
In the second test case, we can choose, for example, a = [-3, -2, -1, 0, 1, 2, 3].
In the third test case, the prefix sums define the only sequence a = [2, 1, 1], but it is not sorted.
In the fourth test case, it can be shown that there is no sequence with the given prefix sums.
In the second test case, we can choose, for example, a = [-3, -2, -1, 0, 1, 2, 3].
In the third test case, the prefix sums define the only sequence a = [2, 1, 1], but it is not sorted.
In the fourth test case, it can be shown that there is no sequence with the given prefix sums.
来源