200982: [AtCoder]ARC098 E - Range Minimum Queries

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

You are given an integer sequence $A$ of length $N$ and an integer $K$. You will perform the following operation on this sequence $Q$ times:

  • Choose a contiguous subsequence of length $K$, then remove the smallest element among the $K$ elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let $X$ and $Y$ be the values of the largest and smallest element removed in the $Q$ operations. You would like $X-Y$ to be as small as possible. Find the smallest possible value of $X-Y$ when the $Q$ operations are performed optimally.

Constraints

  • $1 \leq N \leq 2000$
  • $1 \leq K \leq N$
  • $1 \leq Q \leq N-K+1$
  • $1 \leq A_i \leq 10^9$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$ $Q$
$A_1$ $A_2$ $...$ $A_N$

Output

Print the smallest possible value of $X-Y$.


Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

In the first operation, whichever contiguous subsequence of length $3$ we choose, the minimum element in it is $1$. Thus, the first operation removes $A_3=1$ and now we have $A=(4,3,5,2)$. In the second operation, it is optimal to choose $(A_2,A_3,A_4)=(3,5,2)$ as the contiguous subsequence of length $3$ and remove $A_4=2$. In this case, the largest element removed is $2$, and the smallest is $1$, so their difference is $2-1=1$.


Sample Input 2

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

Sample Output 2

7

Sample Input 3

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

Sample Output 3

451211184

Input

题意翻译

## 题目描述 你有一个长度为 $n$ 的整数序列 $A$,以及一个整数 $K$。你会进行 $Q$ 次操作,一次操作如下: - 选择序列中一个长度为 $K$ 的区间,并且删除区间中的最小元素。如果有多个,你可以选择任何一个。 现在,设 $X$ 是你删除了的元素中最大的一个,$Y$ 是最小的一个,请找出在最优情况下,$X-Y$ 的最小值。 ## 输入格式 请从标准输入中读入: $ N $ $ K $ $ Q $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ ## 输出格式 请输出 $X-Y$ 可能的最小值。 ## 限制 - $1\le K\le N\le 2000$ - $1\le Q\le N-K+1$ - $1\le A_i\le 10^9$ - 输入都是整数

加入题单

上一题 下一题 算法标签: