[BOJ 15479] L番目のK番目の数 (LthKthNumber)

View as PDF

Submit solution

Points: 4
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

横一列に並べられた N 枚のカードがある.左から i 枚目(1 ≦ i ≦ N)のカードには,整数 a_i が書かれている.</p>

JOI 君は,これらのカードを用いて次のようなゲームを行う.連続する K 枚以上のカードの列を選び,次の操作を行う.

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

この操作を,連続する K 枚以上のカードの列すべてに対して行う.すなわち,1 ≦ l ≦ r ≦ N かつ K ≦ r - l + 1 を満たすすべての (l,r) について,a_l, a_{l+1}, ..., a_r のうち K 番目に小さな整数を書き出す.

こうして書き出された整数を,左から小さい順に並べる.並べた整数のうち,左から L 番目のものがこのゲームにおける JOI 君の得点である.JOI 君の得点を求めよ.

입력 형식

入力は以下の形式で標準入力から与えられる.</p>

N K L
a_1 a_2 ... a_N
## 출력 형식

JOI 君の得点を 1 行で出力せよ.

예제 입력 1

4 3 2
4 3 1 2

예제 출력 1

3

예제 입력 2

5 3 3
1 5 2 2 4

예제 출력 2

4

예제 입력 3

6 2 9
1 5 3 4 2 4

예제 출력 3

4

예제 입력 4

6 2 8
1 5 3 4 2 4

예제 출력 4

3

Comments

There are no comments at the moment.