레이팅 미적용소 베시는 컴퓨터 과학에 대한 사랑, 그리고 언젠가 "베시 박사"가 될 수 있다는 매력에 이끌려 컴퓨터 과학 박사 과정에 입학했다. 얼마간 학술 연구를 해 온 베시는 지금까지 논문을 \(N\)편(\(1 \leq N \leq 10^5\)) 발표했고, \(i\)번째 논문은 학계의 다른 논문들로부터 \(c_i\)번(\(0 \leq c_i \leq 10^5\)) 인용되었다.
베시는 학자의 성공을 \(h\)-지수로 측정할 수 있다는 이야기를 들었다. \(h\)-지수란, 연구자가 각각 \(h\)회 이상 인용된 논문을 \(h\)편 이상 가지는 가장 큰 수 \(h\)이다. 예를 들어 논문이 \(4\)편이고 각 인용 횟수가 \((1,100,2,3)\)인 연구자의 \(h\)-지수는 \(2\)이지만, 인용 횟수가 \((1,100,3,3)\)이라면 \(h\)-지수는 \(3\)이 된다.
\(h\)-지수를 올리기 위해, 베시는 각각 자신의 과거 논문 여러 편을 인용하는 서베이 논문을 최대 \(K\)편(\(0 \leq K \leq 10^5\))까지 쓸 계획이다. 하지만 페이지 제한 때문에 각 서베이에서는 논문을 최대 \(L\)편(\(0 \leq L \leq 10^5\))까지만 인용할 수 있다. 물론 한 서베이 안에서 같은 논문을 여러 번 인용할 수는 없다 (하지만 한 논문이 여러 서베이에서 인용될 수는 있다).
이 서베이 논문들을 쓴 뒤 베시가 달성할 수 있는 최대 \(h\)-지수를 구하는 것을 도와주자. 베시는 자신의 서베이에서 다른 서베이를 인용할 수 없다.
참고로, 베시의 지도교수는 언젠가 \(h\)-지수를 올리기 위한 목적만으로 서베이를 쓰는 것은 윤리적으로 의심스러운 행위라고 알려 주어야 할 것이다; 다른 학자들은 여기서 베시를 따라 하지 않기를 권한다.
문제 제공: Dhruv Rohatgi
채점 방식
- 테스트 케이스 1-6은 \(N\le 100\)을 만족한다.
- 테스트 케이스 7-16은 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 \(N\), \(K\), \(L\)이 주어진다.
둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(c_1,\ldots, c_N\)이 주어진다.
최대 \(h\)-지수를 한 줄에 출력한다.
4 4 1
1 100 1 13In this example, Bessie may write up to \(4\) survey articles, each citing at most \(1\) paper.
If she cites each of her first and third articles twice, then her \(h\)-index
becomes
\(3\).
4 1 4
1 100 1 12In this second example, Bessie may write at most a single article. If Bessie cites any
of her first, third, or fourth papers at least once, her \(h\)-index becomes \(2\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Silver