MEANARR - Mean of array

After checking his coders' skills about strings, professor Mahammad wants to analyze how well the coders are familiar with arrays. As the professor is very good at math, he is curious about adding some mathematical background to his new problem. Now, the problem asks you to find the number of subarrays in which the mathematical mean is not less than given K. Mean is the function which defines the average of the corresponding list. More clearly, in order to find the mean of the array, we can divide the sum of the numbers by the number of elements in it. 


The first line of the input contains two positive integers N and K, the number of elements of the array and the mean, respectively. (N ≤ 200000).

The following line contains N integers which represent elements of the array.

All the numbers in the input section are 32-bit positive integers.


Output one integer representing the number of subarrays in which the mean is not less than K.


5 4
5 2 4 5 1


Note: The subarrays, satisfying the condition are: [5], [5, 2, 4, 5], [4], [5], [4, 5].

hide comments
thanos_tapras: 2020-06-03 22:34:40

Nice problem!
Hint: Try to write down the equation that holds true and try to work from there.

bear_grylls: 2018-01-16 19:43:06

can you give some hint

Added by:mahmud2690
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Me, MYSELF & I