파일 업로드

🎨AI 리소스 생성

프롬프트 없음

성공하고싶은 학자의 욕망 I

profile
실행 시간 제한메모리 제한
1 초512 MB
📃 해결할 문제

영훈은 컴퓨터 과학에 대한 애정과 언젠가는 '박사 영훈'으로 불리고 싶은 꿈에 이끌려서 컴퓨터과학 박사 과정에 등록했습니다. 영훈은 지금까지 NN편의 논문을 발행했고 (1N1051 \leq N \leq 10^5), 그의 ii번째 논문은 연구 문헌에서 cic_i 회의 인용을 받았습니다 (0ci1050 \leq c_i \leq 10^5).

영훈은 학자의 성공은 그들의 hh-지수로 측정할 수 있다는 사실을 알았습니다. hh-지수는 연구자가 적어도 hh 편의 논문이 각각 적어도 hh 번 인용된 경우에 가장 큰 수입니다. 예를 들면, 논문 4편을 쓴 연구자의 인용 횟수가 (1,100,2,3)(1,100,2,3) 이면 hh-지수는 22이고, 인용 횟수가 (1,100,3,3)(1,100,3,3)이면 hh-지수는 33입니다.

자신의 hh-지수를 높이기 위해, 영훈은 과거에 쓴 여러 논문을 인용하는 조사 논문을 쓰려고 합니다. 페이지 제한 때문에 이 조사 논문에는 최대 LL회의 인용을 포함할 수 있습니다(0L1050 \leq L \leq 10^5), 그리고 물론 그는 각 논문을 한 번만 인용할 수 있습니다.

이 조사 논문을 쓴 후 영훈이 얻을 수 있는 hh-지수의 최댓값을 알아내 도와주세요.

영훈의 연구 지도 교수는 언젠가 영훈에게 자신의 hh 지수를 늘리기 위해 조사 논문을 쓰는 것은 윤리적으로 문제가 있다고 알려줄 것입니다; 다른 학자들은 여기서 영훈의 사례를 따르지 않는 것이 좋습니다.

💻 입력

입력의 첫 줄에는 NNLL이 주어집니다.

두 번째 줄에는 NN개의 공백으로 구분된 정수 c1,,cNc_1, \ldots, c_N이 주어집니다.

🖨️ 출력

조사 논문을 작성한 후 영훈이 얻을 수 있는 hh-지수의 최댓값을 출력합니다.


💻 예제 입력 1
4 0
1 100 2 3
🖨️ 예제 출력 1
2
💻 예제 입력 2
4 1
1 100 2 3
🖨️ 예제 출력 2
3

💡 힌트

영훈은 과거의 논문들 중 아무것도 인용할 수 없습니다. 위에서 언급했듯이, (1,100,2,3)(1,100,2,3) 에 대한 hh-지수는 22입니다.

 

예제 입력:

4 1
1 100 2 3

예제 출력:

3

영훈이 세 번째 논문을 인용한다면, 인용 횟수는 (1,100,3,3)(1,100,3,3)이 됩니다. 위에서 언급했듯이, 이러한 수치에 대한 hh-지수는 33 입니다.

 

점수 :

  • 테스트 케이스 1-7은 N100N \leq 100을 만족합니다.
  • 테스트 케이스 8-10은 N1000N \leq 1000을 만족합니다.
  • 테스트 케이스 11-17은 N105N \leq 10^5을 만족합니다.

출처: USACO 2021 US Open, Bronze Problem 1. Acowdemia I