시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 468 | 87 | 70 | 26.022% |
2차원 좌표 평면에 변이 축에 평행한 직사각형 N개가 있다. 직사각형은 1부터 N까지 번호가 매겨져 있다. i번 직사각형의 왼쪽 아래 꼭짓점의 좌표는 (xi,1, yi,1)이고, 오른쪽 위 꼭짓점의 좌표는 (xi,2, yi,2)이다. N개의 직사각형 중 K개를 칠해 색칠된 영역의 최댓값을 구해보자.
일부 영역은 하나 이상의 직사각형이 있을 수도 있다. 이 경우 그 영역에 있는 직사각형 중 가장 높은 번호를 가진 직사각형만 보이는 것이다. 예제 1을 참고한다.
첫째 줄에 두 정수 N, K가 주어진다. 둘째 줄부터 N개의 줄에 직사각형을 나타내는 네 정수 xi,1, yi,1, xi,2, yi,2가 주어진다.
첫째 줄에 색칠한 면적을 최대로 하려면, 어떤 직사각형을 칠해야 하는지 출력한다. 빈 칸으로 구분하며, 여러 가지일 경우에는 사전순으로 앞서는 것을 출력한다.
3 2 1 1 5 3 3 2 7 4 2 5 9 7
2 3
7 4 1 1 5 4 2 2 4 3 4 0 6 2 7 1 9 4 1 5 4 7 6 5 9 7 2 5 8 6
1 3 4 7
4 3 -1 -5 1 1 2 2 5 6 -2 3 1 7 2 -4 6 -1
1 2 3