CAN WIN
Time limit2sMemory limit512 MB
Count the subarrays of an array of page word counts whose average is at least P.
- Level
Medium6 of 10
- Topics
- Prefix sum, Binary search, Sorting, Math
- Solved
- No attempts yet
Problem
Ari and Kuki, who attend Catholic University, were studying in Dasol Hall when they began to want a cold coffee.
The weather was so hot that neither wanted to go outside, and they started watching each other's reactions.
Unable to give up on the coffee, the two decided to play the book-opening game, and the loser would go buy the coffee.
The rules of the book-opening game are as follows.
- One person picks any book. (Ari and Kuki pick different books.)
- In the chosen book, that person decides the starting page and the ending page of a range.
- Count the number of English words contained in the range from the starting page to the ending page.
- The score is the number of English words counted divided by the number of pages in the chosen range.
Ari went first and got P points, and when Kuki's turn came, Kuki became curious about the number of cases in which Kuki would not lose to Ari.
Help Kuki and find how many cases there are in which Kuki does not lose to Ari.
Input
The first line gives N, the total number of pages in the book Kuki chose (an integer with 1 ≤ N ≤ 1,000,000), and P, the score Ari got (an integer with 0 ≤ P ≤ 1,000,000,000).
The next line gives W, the number of English words on each page of the book Kuki chose (an integer with 0 ≤ W ≤ 1,000,000,000), N times in order.
Output
Find the number of cases in which Kuki's score is greater than or equal to P (Ari's score).