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.

你所在城市的监狱共有 nn 名囚犯。由于监狱无法容纳所有囚犯,市长决定将其中 cc 名囚犯转移到另一座城市的监狱。

为此,他让这 nn 名囚犯排成一列,每名囚犯胸前写有一个数字,表示其所犯罪行的严重程度。数字越大,表明其罪行越严重。

接着,市长要求你从中选出 cc 名囚犯,送往另一座城市的监狱。他还提出了两个条件:

  • 所选的 cc 名囚犯必须在队列中构成一个连续的区间;
  • 所选囚犯中任意一人的犯罪等级不得超过 tt。因为若超过 tt,该囚犯即被视为重刑犯,而市长不愿承担其在转移途中逃脱的风险。

请计算出你有多少种方式选出这 cc 名囚犯。

输入格式

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.

输入的第一行包含三个用空格分隔的整数 nn(1 ≤ n ≤ 2⋅1051 ≤ n ≤ 2·10^5)、tt(0 ≤ t ≤ 1090 ≤ t ≤ 10^9)和 cc(1 ≤ c ≤ n1 ≤ c ≤ n)。
下一行包含 nn 个用空格分隔的整数,其中第 ii 个整数表示第 ii 位囚犯所犯罪行的严重程度。犯罪严重程度的值为非负整数,且不超过 10910^9。

输出格式

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测评打分。不知道怎么写?

首页