시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 413 | 238 | 187 | 63.176% |
윤헌이는 수강신청 시즌이 되어 시간표를 짜고 있다. 지난 학기 금요일에 수업을 들어 친구들에게 온갖 놀림을 받은 윤헌이는 이번 학기에는 꼭 금요일 공강을 지켜내기로 결심했다!!
고려대학교에서 수강할 수 있는 $n$개의 수업의 요일과 시작 교시, 끝 교시가 주어진다. 요일 $w$는 월요일부터 금요일까지 각각 1부터 5까지의 정수로 주어지며, 수업의 시작 교시 $s$, 끝 교시 $e$가 $1$부터 $10$까지의 정수로 주어진다. 수업의 학점은 $e-s+1$이다.
이번 학기에 $k$ 학점을 듣고 싶은 윤헌이는 금요일에 공강이 있는 시간표의 가짓수가 궁금하다.
이때, 같은 요일, 같은 교시에 열리는 두 수업은 동시에 수강할 수 없다. 예를 들어, 화요일 $5$교시부터 $7$교시까지 열리는 수업과 화요일 $7$교시부터 $9$교시까지 열리는 수업은 동시에 수강할 수 없다.
윤헌이를 위해 정확히 $k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 구해 보자!
첫 줄에 수강 가능한 수업의 개수 $n$과 윤헌이가 듣고 싶은 학점 $k$가 공백으로 구분되어 주어진다.
다음 $i$번째 줄에는 $i$번 수업의 요일, 시작 교시, 끝 교시 $w_i, s_i, e_i$가 공백으로 구분되어 주어진다.
정확히 $k$ 학점을 들으면서 금요일에 수업이 하나도 없는 시간표의 가짓수를 출력한다.
10 15 3 4 4 3 4 9 3 6 8 1 10 10 3 2 5 2 6 10 5 5 5 2 5 7 3 6 10 3 1 6
1
4번 수업, 5번 수업, 6번 수업, 9번 수업을 들으면 1+4+5+5=15학점을 들을 수 있다. 그 이외의 경우는 불가능하다.
화요일 $5$교시부터 $7$교시까지 열리는 수업은 2 5 7과 같이 주어진다.
University > 고려대학교 > 2022 고려대학교 프로그래밍 경시대회 (KCPC mini) > Div. 2 A번
University > 고려대학교 > 2022 고려대학교 프로그래밍 경시대회 (KCPC mini) > Open Contest A번