← 返回题目列表

AtCoder · abc408_f

I. 运动

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 脚手架编号为 1 to N 排成一排。脚手架高度 i(1 \leq i \leq N) is H_i.

高桥决定玩一个在脚手架上移动的游戏。 最初,他自由选择一个整数 i(1 \leq i \leq N) 并登上脚手架 i.

当他在脚手架上时 i 在某个时刻,他可以选择一个整数 j(1 \leq j \leq N) 满足以下条件并移至脚手架 j:

  • H_j \leq H_i - D 和 1 \leq |i-j| \leq R.

求当他重复移动直到不能再移动时他可以移动的最大次数。

约束

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq D,R \leq N
  • H 是一个排列 (1,2,\ldots,N).
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N D R
H_1 H_2 \ldots H_N

输出

输出答案。


示例输入 1

5 2 1
5 3 1 4 2

示例输出 1

2

高桥最初登上脚手架 1 并且可以在脚手架之间移动,如下所示:

  • 第一步:自 H_2 \leq H_1 -D 和 |2-1| \leq R,他可以移动到脚手架 2。从脚手架上移出 1 到脚手架 2.
  • 第二步:自 H_3 \leq H_2 -D 和 |3-2| \leq R,他可以移动到脚手架 3。从脚手架上移出 2 到脚手架 3.
  • 自脚手架高度 3 is 1,他不能再动了。

如上图,他可以移动 2 次。而且,无论他如何选择要移动到的脚手架,他都无法移动 3 或多次。因此,输出 2.


示例输入 2

13 3 2
13 7 10 1 9 5 4 11 12 2 8 6 3

示例输出 2

3