427B.md (1716B)
1 Source: https://codeforces.com/problemset/problem/427/B 2 3 B. Prison Transfer 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The prison of your city has *n* prisoners. As the prison can't accommodate all of them, the city mayor has decided to transfer *c* of the prisoners to a prison located in another city. 22 23 For this reason, he made the *n* prisoners to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was. 24 25 Then, the mayor told you to choose the *c* prisoners, who will be transferred to the other prison. He also imposed two conditions. They are, 26 27 * The chosen *c* prisoners has to form a contiguous segment of prisoners. 28 * Any of the chosen prisoner's crime level should not be greater then *t*. Because, that will make the prisoner a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer. 29 30 Find the number of ways you can choose the *c* prisoners. 31 32 Input 33 34 The first line of input will contain three space separated integers *n* (1 ≤ *n* ≤ 2·105), *t* (0 ≤ *t* ≤ 109) and *c* (1 ≤ *c* ≤ *n*). The next line will contain *n* space separated integers, the *i**th* integer is the severity *i**th* prisoner's crime. The value of crime severities will be non-negative and will not exceed 109. 35 36 Output 37 38 Print a single integer — the number of ways you can choose the *c* prisoners. 39 40 Examples 41 42 Input 43 44 ``` 45 4 3 3 46 2 3 1 1 47 ``` 48 49 Output 50 51 ``` 52 2 53 ``` 54 55 Input 56 57 ``` 58 1 1 1 59 2 60 ``` 61 62 Output 63 64 ``` 65 0 66 ``` 67 68 Input 69 70 ``` 71 11 4 2 72 2 2 0 7 3 2 2 4 9 1 4 73 ``` 74 75 Output 76 77 ``` 78 6 79 ```