시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 70 23 12 28.571%

문제

SPC(Sogang Premium Cake) 제과점은 직사각형 릿이 올려진 직사각형 모양의 케익만 판매한다.

Mr. K는 심심하지 않게 케익 조각을 다음과 같은 방법으로 잘라 먹으려고 한다.


- 예제 입력 1에 대해 케이크를 자를 수 있는 방법들 -

  1. 그림과 같이 가로와 세로의 길이가 $W$, $H$인 SPC케익을 1사분면 위에 고정한다.
  2. 케익의 꼭짓점을 포함한 오른쪽과 윗변 위의 정수 좌표의 점들 중 두 개($A$, $B$)를 $L = \left|x_A-x_B\right|+\left|y_A-y_B\right|$이 되도록 선택한다.
  3. 케익의 왼쪽 아래 꼭짓점 $O(0, 0)$으로부터 선분 $\overline{OA}$, $\overline{OB}$를 긋는다.
  4. 선분 $\overline{OA}$, $\overline{OB}$에 둘러싸인 케익 조각을 잘라내어 먹는다. 이 때, Mr.K는 선분으로 잘려진 릿은 먹지 않고 온전히 남아 있는 릿만 먹는다. 이 때, 선분이 릿을 관통하지 않고 꼭짓점과만 만날 때는 잘리지 않은 것으로 간주한다.
  5. 릿은 서로 겹치지 않고, 케익의 모서리에 닿지 않으며, 그림과 같이 좌표축에 평행하도록 케익 내부에 놓여 있다.

주치의인 당신은 그가 릿을 얼마나 먹게 될지 궁금해졌다. Mr.K가 케익을 잘랐을 때 먹을 수 있는 릿 면적 합의 최댓값을 구해보자!

주어진 그림에서 왼쪽과 같이 자를 경우 릿 면적 합은 $7$ 로 최대한 먹을 수 있고, 오른쪽의 경우는 $5$만큼 밖에 먹지 못한다.

입력

첫째 줄에 정수 $W$, $H$, $L$, $N$이 주어진다. 

  • $5 \leq W, H \leq 100\ 000$
  • $1<L<W+H$
  • $1 \leq N \leq \min\left\{100\ 000, (W-2) \times (H-2)\right\}$

둘째 줄부터 $N$개 줄에 정수 $x$, $y$, $w$, $h$가 주어진다. $\left(x, y\right)$는 초콜릿 조각의 왼쪽 아래 꼭짓점의 좌표, $\left(w, h\right)$는 초콜릿 조각의 가로와 세로 길이이다.

출력

Mr.K가 먹을 수 있는 초콜릿 넓이 합의 최댓값을 출력한다.

예제 입력 1

8 8 8 5
3 1 4 1
1 1 1 6
3 3 1 2
6 4 1 1
4 5 2 2

예제 출력 1

7

출처

University > 서강대학교 > 2020 Sogang Programming Contest Open R번