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


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

  1. a1 ≤ a2 ≤⋯≤ an, and
  2. 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.
输出格式
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.
上传者
提交记录查看记录
题目类型传统
评测方式文本比较
提交 / 通过136 / 34
相关讨论
暂无讨论