CF427B.Prison Transfer
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
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.
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,
- The chosen c prisoners has to form a contiguous segment of prisoners.
- 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.
Find the number of ways you can choose the c prisoners.
你所在城市的监狱共有 n 名囚犯。由于监狱无法容纳所有囚犯,市长决定将其中 c 名囚犯转移到另一座城市的监狱。
为此,他让这 n 名囚犯排成一列,每名囚犯胸前写有一个数字,表示其所犯罪行的严重程度。数字越大,表明其罪行越严重。
接着,市长要求你从中选出 c 名囚犯,送往另一座城市的监狱。他还提出了两个条件:
- 所选的 c 名囚犯必须在队列中构成一个连续的区间;
- 所选囚犯中任意一人的犯罪等级不得超过 t。因为若超过 t,该囚犯即被视为重刑犯,而市长不愿承担其在转移途中逃脱的风险。
请计算出你有多少种方式选出这 c 名囚犯。
输入格式
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.
输入的第一行包含三个用空格分隔的整数 n(1 ≤ n ≤ 2⋅105)、t(0 ≤ t ≤ 109)和 c(1 ≤ c ≤ n)。
下一行包含 n 个用空格分隔的整数,其中第 i 个整数表示第 i 位囚犯所犯罪行的严重程度。犯罪严重程度的值为非负整数,且不超过 109。
输出格式
Print a single integer — the number of ways you can choose the c prisoners.
输出一个整数——选择 c 名囚犯的方法数。
输入输出样例
输入#1
4 3 3 2 3 1 1
输出#1
2
输入#2
1 1 1 2
输出#2
0
输入#3
11 4 2 2 2 0 7 3 2 2 4 9 1 4
输出#3
6
输入解题思路,AI测评打分。不知道怎么写?