22031번 - 회의실 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 278 | 101 | 51 | 33.117% |
문제
$K$개의 회의실이 있다. $N$개의 회의가 이 회의실들을 이용하려고 한다. 각 회의는 $1$부터 $N$까지 번호가 붙어 있다. 회의 $i$는 시작 시각 $s_i$, 끝나는 시각 $e_i$, 위약금 $w_i$로 표현된다.
이 회의실들은 매우 특이한 규칙에 따라 운영된다. 회의 $i$와 회의 $j$는 다음 조건 중 적어도 하나를 만족하면 관련있는 회의라고 부른다.
- 두 구간 $[s_i , e_i]$와 $[s_j , e_j]$의 공통된 구간이 존재할 때 (시작과 끝 시각만 겹치는 경우에도) $i$와 $j$는 관련있는 회의이다.
- 두 구간 $[s_i , e_i]$와 $[s_j , e_j]$의 공통된 구간이 존재하지 않지만, 다른 회의 $c$가 $i$와 관련있고 $[s_c , e_c]$와 $[s_j , e_j]$의 공통된 구간이 존재할 때 (시작과 끝 시각만 겹치는 경우에도) $i$와 $j$는 관련있는 회의이다.
회의들이 취소될 수 있어서 위의 정의는 취소되지 않은 회의들만 가지고 판단한다. 즉, 원래 관련있는 회의 관계였던 두 회의가, 일부 회의의 취소로 인해 관련있는 회의 관계가 아니게 될 수 있다.
취소되지 않은 회의는 회의실을 하나씩 할당받아야 한다. 관련있는 회의들은 모두가 반드시 서로 다른 회의실을 할당받아야 한다. 예를 들어 세 회의 $[1,3]$, $[3,5]$, $[5,7]$는, $[1, 3]$과 $[5, 7]$ 사이에 공통된 구간이 없음에도 불구하고, 두 개가 아닌 세 개의 회의실을 할당받아야 함에 유의하시오. 회의실이 $K$개밖에 없기 때문에 일부 회의들을 취소해야 할 수 있다. 회의 $i$를 취소하면 위약금 $w_i$를 내야 하므로, 가급적 취소할 회의를 잘 골라서 지급할 위약금의 합을 최소로 하고 싶다.
다음 그림은 5개의 회의 $[1, 4]$, $[3, 6]$, $[5, 8]$, $[7, 10]$, $[9, 12]$가 있고, 각 회의의 위약금이 차례로 1, 2, 5, 2, 1인 경우를 보이고 있다. 회의실이 2개 있다고 하자. 왼쪽의 예는 $[5, 8]$을 취소해서 조건을 만족시키는 경우이며, 이 경우 위약금은 $5$이다. 오른쪽의 예는 $[3, 6]$과 $[9, 12]$를 취소해서 조건을 만족시키는 경우이며, 이 경우 위약금은 $3$이다. 모든 경우를 고려해보면 최소의 위약금 합은 $3$임을 알 수 있다.
입력
첫째 줄에 공백으로 구분된 두 정수 $N$, $K$가 주어진다.
다음 $N$개의 줄에는 공백으로 구분된 세 정수 $s_i$, $e_i$, $w_i$가 주어진다.
출력
주어진 회의실의 수와 회의 정보를 바탕으로, 조건을 만족하게 하기 위해서 취소해야 할 회의들 중 가장 위약금의 합이 적은 경우를 찾고 그때의 위약금의 합을 출력한다.
제한
- $1 \le K \le N$
- $1 \le N \le 2\,500$
- $1 \le s_i \le e_i \le 10^9$ $(1 \le i \le N)$
- $1 \le w_i \le 10^9$ $(1 \le i \le N)$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \le 16$ |
| 2 | 17 | $K = 1$ |
| 3 | 32 | 모든 $i$에 대해 $w_i = 1$ |
| 4 | 26 | $N \le 250$ |
| 5 | 65 | 추가적인 제약 조건이 없다. |
예제 입력 1
5 2 1 4 1 3 6 2 5 8 5 7 10 2 9 12 1
예제 출력 1
3
출처
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon E번
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2021 > 2차 선발고사 2번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon E번
- 문제를 만든 사람: koosaga
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호