Score : $600$ points
You are given an integer sequence of length $N$, $a =$ {$a_1, a_2, …, a_N$}, and an integer $K$.
$a$ has $N(N+1)/2$ non-empty contiguous subsequences, {$a_l, a_{l+1}, …, a_r$} $(1 ≤ l ≤ r ≤ N)$. Among them, how many have an arithmetic mean that is greater than or equal to $K$?
Input is given from Standard Input in the following format:
$N$ $K$ $a_1$ $a_2$ $:$ $a_N$
Print the number of the non-empty contiguous subsequences with an arithmetic mean that is greater than or equal to $K$.
3 6 7 5 7
5
All the non-empty contiguous subsequences of $a$ are listed below:
Their means are $7$, $6$, $19/3$, $5$, $6$ and $7$, respectively, and five among them are $6$ or greater. Note that {$a_1$} and {$a_3$} are indistinguishable by the values of their elements, but we count them individually.
1 2 1
0
7 26 10 20 30 40 30 20 10
13