405354: GYM101911 K Medians and Partition

Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array $$$[10, 3, 2, 3, 2]$$$ is $$$3$$$ (i.e. $$$[2, 2, \underline{3}, 3, 10]$$$). Median of the array $$$[1, 5, 8, 1]$$$ is $$$1$$$ (i.e. $$$[1, \underline{1}, 5, 8]$$$).

Let array be $$$m$$$-good if its median is greater or equal than $$$m$$$.

Let the partition of array $$$[a_1, a_2, \dots, a_n]$$$ be a set of subarrays $$$\{b_1, b_2, \dots, b_k\}$$$ such that $$$b_1 = [a_1, a_2, \dots, a_{i_1}]$$$, $$$b_2 = [a_{i_1 + 1}, a_{i_1 + 2}, \dots, a_{i_2}]$$$, ..., $$$b_k = [a_{i_{k-1} + 1}, a_{i_{k-1} + 2}, \dots, a_n]$$$. For example, array $$$[10, 3, 2, 3, 2]$$$ can be partitioned as follows: $$$\{[10, 3, 2, 3, 2]\}$$$ or $$$\{[10], [3], [2], [3], [2]\}$$$, or $$$\{[10], [3, 2, 3, 2]\}$$$, or $$$\{[10, 3], [2], [3, 2]\}$$$ and so on.

You are given array $$$a$$$ of length $$$n$$$ and integer $$$m$$$. Find the partition of $$$a$$$ into maximum number of subarrays such that each subarray is $$$m$$$-good.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5\,000$$$, $$$1 \le m \le 5\,000$$$) — length of array $$$a$$$ and constant $$$m$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 5\,000$$$)— array $$$a$$$.

If there is no valid partition of array $$$a$$$ into $$$m$$$-good subarrays, print $$$0$$$. Otherwise print maximum number of subarrays in partition of array $$$a$$$ such that each subarray is $$$m$$$-good.

5 2
10 3 2 3 2

5

5 3
10 3 2 3 2

1

5 4
10 3 2 3 2

0

In the first example array can be partitioned into $$$5$$$ subarrays: $$$\{[10], [3], [2], [3], [2]\}$$$. Medians of each part greater of equal than $$$2$$$.

In the second example we can't partition array into several subarrays since medians of $$$[2]$$$, $$$[3, 2]$$$, $$$[2, 3, 2]$$$ and $$$[3, 2, 3, 2]$$$ are less than $$$3$$$.