← 返回题目列表

AtCoder · arc098_c

E. 最小查询范围

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

分数: 600 点

问题陈述

给你一个整数序列 A 长度 N 和一个整数 K。 您将对此序列执行以下操作 Q 次:

  • 选择长度连续的子序列 K,然后删除其中最小的元素 所选子序列中包含的 K 元素(如果有多个此类元素,请选择其中一个)。

让 X 和 Y 是删除的最大和最小元素的值 Q 操作。你想要 X-Y 尽可能小。 找到最小的可能值 X-Y 当 Q 操作以最佳方式执行。

约束

  • 1 \leq N \leq 2000
  • 1 \leq K \leq N
  • 1 \leq Q \leq N-K+1
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

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

N K Q
A_1 A_2 ... A_N

输出

打印最小可能值 X-Y.


示例输入 1

5 3 2
4 3 1 5 2

示例输出 1

1

在第一个操作中,取长度连续的子序列 3 我们选择,里面的最小元素是 1。 因此,第一个操作删除了 A_3=1 现在我们有 A=(4,3,5,2)。 在第二次操作中,最优选择 (A_2,A_3,A_4)=(3,5,2) 作为长度的连续子序列 3 并删除 A_4=2。 在这种情况下,删除的最大元素是 2,最小的是 1,所以他们的区别是 2-1=1.


示例输入 2

10 1 6
1 1 2 3 5 8 13 21 34 55

示例输出 2

7

示例输入 3

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

示例输出 3

451211184