시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 38 | 36 | 31 | 93.939% |
横一列に並べられた N 枚のカードがある.左から i 枚目(1 ≦ i ≦ N)のカードには,整数 a_i が書かれている.
JOI 君は,これらのカードを用いて次のようなゲームを行う.連続する K 枚以上のカードの列を選び,次の操作を行う.
この操作を,連続する K 枚以上のカードの列すべてに対して行う.すなわち,1 ≦ l ≦ r ≦ N かつ K ≦ r - l + 1 を満たすすべての (l,r) について,a_l, a_{l+1}, ..., a_r のうち K 番目に小さな整数を書き出す.
こうして書き出された整数を,左から小さい順に並べる.並べた整数のうち,左から L 番目のものがこのゲームにおける JOI 君の得点である.JOI 君の得点を求めよ.
入力は以下の形式で標準入力から与えられる.
N K L a_1 a_2 ... a_N
JOI 君の得点を 1 行で出力せよ.
번호 | 배점 | 제한 |
---|---|---|
1 | 6 | N ≦ 100 |
2 | 33 | N ≦ 4000 |
3 | 61 | 追加の制限はない. |
4 3 2 4 3 1 2
3
1 ≦ l ≦ r ≦ N (= 4) かつ K (= 3) ≦ r - l + 1 を満たす (l,r) は,(1,3), (1,4), (2,4) の 3 通りある.
これらの (l,r) に対し,a_l, a_{l+1}, ..., a_r で 3 番目に小さな整数は,それぞれ 4, 3, 3 である.
このうち L (= 2) 番目に小さい整数は 3 なので,JOI 君の得点は 3 である.同じ整数が複数あるときも,重複して数えることに注意せよ.
5 3 3 1 5 2 2 4
4
JOI 君が書き出す整数は,
である.このうち L (= 3) 番目に小さい整数は 4 である.
6 2 9 1 5 3 4 2 4
4
6 2 8 1 5 3 4 2 4
3
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2017/2018 예선 6번