| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 559 | 338 | 285 | 59.375% |
이 문제는 지정좌석 배치하기 2 문제와 마지막 문단 및 출력만 다릅니다. 지정좌석 배치하기 2 문제의 코드로 이 문제를 해결할 수 없음에 유의하세요.
UDP대학교의 인기 교수 달구 교수님의 이번 학기 강의실은 정원이 $N \times M$명인 강의실로 배정되었으며, $N$행 $M$열의 직사각형 모양으로 좌석이 배치되어 있다. 해당 강의실은 뒤에 앉은 학생도 원활히 강의를 수강할 수 있도록 각 행의 좌석 높이가 $D$씩 차이가 나며, 가장 앞에 위치한 행부터 뒤에 위치한 행까지 순서대로 1ドル$행, 2ドル$행, $\cdots,ドル $N$행이라고 할 때 $i$행의 좌석 높이는 $D\times i$이다.
달구 교수님은 원활한 출석체크를 위해 지정좌석제를 실시하기 때문에, $N \times M$명의 모든 학생은 한 학기 동안 동일한 좌석에만 앉을 수 있다. 달구 교수님은 학생들이 최대한 본인이 원하는 좌석에 앉을 수 있도록 각 학생이 희망하는 좌석의 행을 조사하였고, 그 결과 각 행에 앉기를 희망하는 학생들을 $M$명씩 선정하였다. 그중 $i$행의 좌석을 희망하는 학생의 키는 각각 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$이다.
학생들의 원활한 강의 수강을 위해, 각 학생의 시야가 같은 열에 앉은 다른 학생에 의해 가려지는 경우가 없도록 좌석을 배치하고자 한다. 구체적으로, 각 학생의 (좌석 높이 + 키)는 자신보다 앞 행의 같은 열에 있는 모든 학생의 (좌석 높이 + 키)보다 커야 한다.
좌석을 배치하던 달구 교수님은, 학생들의 시야를 확보하면서 모든 학생을 희망하는 행에 앉히는 것이 불가능할 수도 있다는 것을 깨달았다. 각 행에 앉고자 하는 학생의 키가 주어졌을 때, 주어진 조건에 맞게 모든 학생을 원하는 행의 좌석에 배치할 수 있는지 여부를 구해주자.
첫 번째 줄에 강의실 좌석의 행 개수 $N,ドル 열 개수 $M$과 각 행의 높이 차이를 의미하는 정수 $D$가 공백으로 구분되어 주어진다. $(1\leq N, M\leq 1,000円;$ 1ドル\leq D\leq 100,000円)$
이후 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $i$행 좌석에 앉고자 하는 학생 $M$명의 키를 의미하는 정수 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$이 공백으로 구분되어 주어진다. $(1\leq h_{i,j}\leq 100,000円)$
주어진 조건에 맞게 모든 학생을 원하는 행의 좌석에 배치할 수 있다면 YES, 불가능하다면 NO를 출력한다.
3 3 3 1 2 5 4 1 4 5 2 2
YES
가장 앞에 위치한 행부터 순서대로 앉는 학생의 키를 각각 $\{2, 5, 1\},ドル $\{4, 4, 1\},ドル $\{2, 5, 2\}$ 순서로 좌석을 배치하면 (좌석 높이 + 학생의 키)는 각각 $\{5, 8, 4\},ドル $\{10, 10, 7\},ドル $\{11, 14, 11\}$이 되어 모든 학생이 시야를 확보하며 원하는 행의 좌석에 앉을 수 있다.
2 1 5 8 2
NO
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Junior Division C번
University > UNIST-DGIST-POSTECH > 2024 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2024 UDPC) > Open Contest C1번