Problem : 348 - B. 小紫愛塗色

Problem Statistics

Solved Member: 7　　Submission: 87　　User Tried: 12

Statement:

小紫是個有點害羞的平凡高中生，她平常沒事的時候喜歡亂塗顏色。
有一天，小紫看到了一連串的方格，她數了一下，總共有n個方格排成一列，由於小紫最近沉迷於到處上色，因此她就想要把這些方格都塗上一些顏色。就在她準備塗色時，她發現每個方格上都有一個數字，此時小紫突然覺得就這麼亂塗顏色太無趣了，因此她決定她的塗色結果要滿足兩個規則：
1. 每種顏色都只能用一次，且一次只能塗一個連續的區間。
2. 每個數字都一定要被塗上顏色。
3. 在相同顏色的區塊中，格子上面的數字的平均值必須嚴格大於k。
但定了這些規則後，她發現要滿足這些條件可不容易。因此小紫想要問你，在最佳的塗色方法下，最多可以塗上幾個顏色?

Input:Output:

第一行有一個整數T，表示再來有幾筆測試資料。
每筆測試資料的第一行有兩個整數n, k，同題目敘述。
下一行會有n個整數，第i個數字ai表示第i個方格上的數字。

對每筆輸入資料請輸出一行，表示小紫最多可以塗幾種顏色。如果無法塗上任何顏色，請輸出”0”(不含引號)。

Sample Input:Sample Output:

2
5 2
2 3 4 3 2
2 2
1 2

3
0

HINT:

20 % 1 <= n <= 10、1 <=ai, k <= 500
60 % 1 <= n <= 1,000、1 <= ai, k <= 1,000,000,000
100% 1 <= n <= 500,000、1 <= ai, k <= 1,000,000,000

第一筆測資中，可以把序列分為[2, 3], [4], [3, 2]，因此可以塗上三種顏色。

Source:

2014 延平校內賽

Problem Setter

rilak

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	20
2	1000ms	262144kb	20
3	3000ms	262144kb	20
4	3000ms	262144kb	20
5	3000ms	262144kb	20