시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 557 | 202 | 153 | 38.636% |
무한히 넓은 당근 밭 가운데 $x$, $y$ 축으로 수평인 직사각형 마구간이 있다. 그림 B.1 의 왼쪽 그림처럼 마구간의 왼쪽 아래 모서리 기둥에 말이 묶여 있고, 마구간의 네 모서리는 모두 격자점에 있다. 상하좌우로 인접한 두 격자점 사이의 간격은 $1$이다. 말을 묶은 줄의 길이는 $L$로 유한하다. 그리고 당근 밭의 모든 격자점마다 하나씩 당근이 심어져 있다. 그리고 말을 묶은 줄이 닿을 수 있는 거리 안에 심어진 당근은 말이 모두 먹을 수 있다고 가정한다.
만일 마구간의 크기가 11 × 6이고 묶은 줄의 길이가 9일때, 말이 먹을 수 있는 당근이 그림 B.1 의 오른쪽 그림에서 점으로 표시되어 있다. 단, 말과 말을 묶은 줄은 마굿간안으로는 들어갈 수 없으며 마굿간의 경계와 내부에는 당근이 심어져 있지 않다.
그림 B.1 (왼쪽) 마구간과 길이 9 인 줄에 묶인 말. (오른쪽) 말이 먹을 수 있는 모든 당근 (점).
마구간의 크기 $w \times h$ 와 말을 묶은 줄의 길이 $L$, 이렇게 3 개의 정수 $w$, $h$, $L$ 이 주어졌을 때, 말이 먹을 수 있는 당근의 최대 개수를 구하는 프로그램을 작성하시오. 격자점과 말을 묶은 기둥과의 거리가 정확하게 $L$인 경우, 이 격자점의 당근은 말이 먹을 수 있음에 유의하자.
입력은 표준입력을 사용한다. 첫 번째 줄에 마구간의 크기와 줄의 길이를 나타내는 3 개의 양의 정수 $w$, $h$, $L$ ($1 \le w, h, L \le 100,000$)가 주어진다.
출력은 표준출력을 사용한다. 주어진 조건에서 말이 먹을 수 있는 당근의 최대 개수를 첫 번째 줄에 정수로 출력한다.
11 6 3
18
그림 B.2 첫 번째 테스트 케이스에 대한 설명
11 6 15
591
11 6 20
1134