31816번 - Closet 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 180 | 53 | 40 | 28.369% |
문제
태인이의 옷장에는 $N$개의 옷이 일렬로 걸려 있다. 현재 왼쪽에서 $i$번째 옷의 색은 $c_i$이다.
태인이는 어떤 정수 $k$ ($1\le k\le N$)가 존재해 $c_1\leq c_2\leq\cdots\leq c_k\geq c_{k+1}\geq\cdots\geq c_N$를 만족하면 옷장이 아름답다고 생각한다.
하지만 옷장을 아름다운 상태로 정리하는 것은 꽤 귀찮다. 그래서 태인이는 옷장에서 최대 $M$개의 옷을 제거해 남은 옷들을 거의 아름다운 상태로 만들기로 했다.
최대 $M$개의 옷을 제거한 후, 남은 옷들의 개수를 $L$, 왼쪽에서 $j$번째 옷의 색을 $d_j$라 하자. 태인이는 인접한 두 옷의 색의 차가 $x$ 이하라면 두 옷을 같은 색으로 인식하기로 했다. 즉, 다음을 만족하는 정수 $k$ ($1\le k\le L$)가 존재한다면 옷장이 거의 아름다운 상태라고 한다.
- $1\leq j<k$인 모든 정수 $j$에 대해 $d_j-d_{j+1}\leq x$.
- $k\leq j<L$인 모든 정수 $j$에 대해 $d_{j+1}-d_j\leq x$.
$M$개 이하의 옷을 제거해 옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 음이 아닌 정수 $x$의 값을 구하자.
입력
첫 번째 줄에 두 정수 $N$과 $M$이 주어진다.
두 번째 줄에 $N$개의 정수 $c_1,c_2,\ldots ,c_N$가 공백을 사이에 두고 주어진다.
출력
옷장을 거의 아름다운 상태로 만들 수 있는 가장 작은 $x$ ($x\ge 0$)의 값을 출력한다.
제한
- $1\leq N\leq 10^5$
- $0\leq M\leq N$
- $1\leq c_i\leq 10^9$ ($1\leq i\leq N$)
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $M=0$ |
| 2 | 21 | $1 \leq N \leq 1\,000$ |
| 3 | 16 | $1 \leq c_i \leq 100$ ($1 \leq i \leq N$) |
| 4 | 59 | 추가적인 제약 조건이 없다. |
예제 입력 1
10 2 4 2 7 15 3 11 12 10 2 6
예제 출력 1
2
노트
$x=2$일 때, 왼쪽에서 5번째 옷과 9번째 옷을 제거하면 옷장은 거의 아름다운 상태가 된다. 이보다 더 작은 $x$로는 옷장을 거의 아름다운 상태로 만들 수 없다.
출처
University > KAIST > KAIST RUN Spring Contest > 2024 KAIST RUN Spring Contest D번
- 문제를 만든 사람: abra_stone
- 문제를 검수한 사람: 79brue, flappybird, koosaga, octane, parkky
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호