A14685 | $Keep the Average High$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given an array of integers $a_1, a_2, \ldots, a_n$ and an integer $x$ . You need to select the maximum number of elements in the array, such that for every subsegment $a_l, a_{l + 1}, \ldots, a_r$ containing strictly more than one element $(l < r)$ , either: - At least one element on this subsegment is not selected, or - $a_l + a_{l+1} + \ldots + a_r \geq x \cdot (r - l + 1)$ .

The first line of input contains one integer $t$ ( $1 \leq t \leq 10$ ): the number of test cases. The descriptions of $t$ test cases follow, three lines per test case. In the first line you are given one integer $n$ ( $1 \leq n \leq 50\,000$ ): the number of integers in the array. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-100\,000 \leq a_i \leq 100\,000$ ). The third line contains one integer $x$ ( $-100\,000 \leq x \leq 100\,000$ ).

For each test case, print one integer: the maximum number of elements that you can select.

输入 #1

4
5
1 2 3 4 5
2
10
2 4 2 4 2 4 2 4 2 4
3
3
-10 -5 -10
-8
3
9 9 -3
5

输出 #1

C++ 编辑器

输入

输出