10717번 - 성벽 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 512 MB | 238 | 97 | 67 | 41.104% |
문제
역사학자인 JOI 교수는 이전에 존재했던 IOI 왕국에 대해 연구하고 있다.
과거의 조사에 따르면, IOI 왕국은 세로 H 크기에 가로 W 크기이며, IOI 왕국의 수도는 방어를 위해 성벽으로 둘러싸여 있었다.
IOI 왕국의 수도를 둘러싸는 성벽은 다음과 같은 형태를 하고 있다:
- 성벽의 크기 s(s ≥ 3)가 있다.
- 크기 s의 성벽은 s × s의 정사각형 영역에서 안의 (s-2) × (s-2) 정사각형 영역을 제외한 테두리 모양을 하고 있다.
또 다른 조사에 의하면, 수도를 둘러싼 성벽의 크기는 L 이상이었다. 그리고 어떤 칸들에는 오래된 나무가 있는데, 나무가 있는 위치에는 성벽이 존재하지 않았음을 알고 있다.
JOI 교수는 이러한 사실들을 바탕으로 있을 수 있는 성벽의 가지 수를 알고 싶어한다. 이때, 성벽의 크기가 같더라도 위치가 다르면 서로 다른 성벽으로 간주한다.
IOI 왕국의 크기와, 성벽의 최소 크기, 그리고 나무의 위치들이 주어졌을 때 가능한 성벽의 가지 수를 구하는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 정수 H, W, L, P가 공백으로 구분되어 주어진다. 이는 IOI 왕국의 크기가 세로 H, 가로 W이며 성벽의 최소 크기는 L, 나무의 개수가 P라는 뜻이다.
다음 P 개의 줄에 나무의 위치가 Ai, Bi가 공백으로 구분되어 주어진다. 이는 나무가 Ai번째 줄, Bi번째 칸에 있음을 의미한다.
출력
첫 줄에 가능한 성벽의 가지 수를 출력한다.
제한
- 1 ≦ H, W ≦ 4 000
- 3 ≦ L ≦ min(H, W)
- 0 ≦ P ≦ 100 000
- 1 ≦ Ai ≦ H (1 ≦ i ≦ P)
- 1 ≦ Bi ≦ W (1 ≦i ≦ P)
- (Ai, Bi) ≠ (Aj, Bj) (1 ≦ i < j ≦ P)
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | H ≦ 500, W ≦ 500. |
| 2 | 16 | 0 ≦ P ≦ 10. |
| 3 | 80 | 추가적인 제약 조건이 없다. |
예제 입력 1
5 5 3 2 2 2 4 3
예제 출력 1
4
1번 예제에서 가능한 성벽은 아래 4가지이다. 나무는 x로 표시되어있다.
예제 입력 2
7 8 4 3 2 2 3 7 6 5
예제 출력 2
13
예제 입력 3
4000 4000 1234 4 1161 3028 596 1892 3731 2606 702 1530
예제 출력 3
7050792912
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호