레이팅 미적용농부 존은 멀티태스킹에 서투르다. 그는 자주 딴 데 정신이 팔려서 긴 작업을 끝마치기 어려워한다. 지금 그는 헛간의 한쪽 면을 칠하려 하고 있는데, 작은 직사각형 영역들을 칠하다가 소를 돌보는 일에 정신이 팔리기를 반복하는 바람에, 헛간의 어떤 부분은 다른 부분보다 페인트가 더 여러 겹 칠해진 상태가 되었다.
헛간의 한쪽 면을 2차원 \(x\)-\(y\) 평면으로 나타낼 수 있으며, 농부 존은 그 위에 \(N\)개의 직사각형을 칠한다. 각 직사각형은 변이 좌표축에 평행하며, 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표로 주어진다.
농부 존은 가까운 시일 내에 다시 칠할 필요가 없도록 헛간에 페인트를 여러 겹 칠하고 싶다. 하지만 지나치게 많은 겹을 칠하느라 시간을 낭비하고 싶지는 않다. 알고 보니 \(K\)겹의 페인트가 최적의 양이라고 한다. 그런데 \(K\)겹의 페인트로 덮인 넓이를 보니 존은 그리 만족스럽지 않다. 존은 이 넓이를 늘리기 위해 최대 두 개의 직사각형을 추가로 칠할 의향이 있다. 단, 이 두 직사각형은 서로소여야 한다(양의 넓이를 공유하지 않아야 한다). 새 직사각형을 하나만 칠하거나 아예 칠하지 않는 것이 최선이라면 그렇게 할 수도 있다는 점에 유의하라.
문제 제공: Nick Wu and Brian Dean
문제 제공: Nick Wu and Brian Dean
첫째 줄에 \(N\)과 \(K\) (\(1 \leq K, N \leq 10^5\))가 주어진다. 남은 \(N\)개의 줄 각각에는 칠해지는 직사각형 영역을 나타내는 네 정수 \(x_1, y_1, x_2, y_2\)가 주어지며, 왼쪽 아래 꼭짓점은 \((x_1, y_1)\), 오른쪽 위 꼭짓점은 \((x_2, y_2)\)이다. 모든 \(x\)와 \(y\) 값은 \(0 \ldots 200\) 범위이며, 모든 직사각형은 양의 넓이를 가진다.
농부 존이 서로소인 직사각형을 최대 두 개 추가로 칠할 때, 정확히 \(K\)겹의 페인트로 덮일 수 있는 헛간 넓이의 최댓값을 출력한다.
paintbarn.in · 출력을 쓸 파일 paintbarn.out3 2
1 1 4 4
3 3 7 6
2 2 8 726riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Gold