← 返回题目列表

AtCoder · awc0108_e

E. 路灯检查

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

分数: 466 分

问题陈述

高桥是市政府的一名员工,负责管理某条道路上的路灯。

有 N 路灯沿着这条路排成一排,从左到右编号为路灯 1,路灯 2, \ldots,路灯 N。每盏路灯 i (1 \leq i \leq N) 有一个整数参数 S_i。该参数代表路灯的亮度,但对于故障路灯来说它可能为负值。

高桥需要暂时关闭路灯 T 以便更换灯泡。关闭时,路灯的亮度 T 被视为 0 无论其原始值如何 S_T.

根据本市安全标准,对于由以下部分组成的路段 K 连续路灯,将该路段内所有路灯中的最低亮度定义为该路段的“安全等级”。安全级别较低意味着该区域更暗且更危险。

虽然路灯 T 已关闭,高桥想要计算每个部分的安全级别 K 连续路灯,包括路灯 T,并确定其中的最大值。

更准确地说,考虑所有整数 l 满足以下条件:

  • 1 \leq l 和 l + K - 1 \leq N
  • l \leq T \leq l + K - 1 (该部分包括路灯 T)

对于每个 l,该部分的安全级别 [l, l+K-1] 定义如下。对于每个整数 i 满意 l \leq i \leq l+K-1,让

A_i = \begin{cases} 0 & (i = T) \\ S_i & (i \neq T) \end{cases}

然后其中的最小值 A_l, A_{l+1}, \ldots, A_{l+K-1} 是本节的安全级别。

计算所有的安全级别 l 满足条件,输出其中的最大值。

请注意,在给定的约束下,始终存在至少一个 l 满足条件。

约束

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq T \leq N
  • -10^9 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数

输入

N K T
S_1 S_2 \ldots S_N
  • 第一行包含三个空格分隔的整数: N 代表路灯数量, K 代表一段的长度,以及 T 代表要关闭的路灯编号。
  • 第二行包含空格分隔的整数 S_1, S_2, \ldots, S_N 代表每个路灯的亮度。

输出

在一行中输出所有部分中的最大安全级别 K 连续路灯,包括路灯 T,当路灯亮时 T 已关闭。


示例输入 1

5 3 3
2 -1 7 3 1

示例输出 1

0

示例输入 2

6 3 4
-5 3 2 10 -3 4

示例输出 2

0

示例输入 3

10 4 5
3 -2 5 1 8 -4 7 2 6 -1

示例输出 3

-2

示例输入 4

20 5 12
4 -3 7 2 -1 8 5 -6 3 9 1 100 -2 6 4 -7 3 8 2 -5

示例输出 4

-2

示例输入 5

1 1 1
1000000000

示例输出 5

0