메뉴 건너뛰기

문제

18nm3 물 탱크 0  

시간메모리제출 올바른 답 비율
6초256MB
1
1
100.0%


나의 횟수나의 최근 판정시도 성공 비율
11
100.0%
물 탱크 

세로 길이가 NN, 가로 길이가 MM, 높이가 HH인 물탱크가 있다. NN, MM, HH는 모두 양의 정수이다. <그림 1>은 세로 길이가 22, 가로 길이가 33, 높이가 55인 물탱크 모양을 보여준다. <그림 1>에서 보듯이 물탱크 내부는 가로와 세로로 벽이 설치되어 있는데, 내부 각 칸(즉 사각기둥 모양)의 세로와 가로 길이는 1이고 높이는 H가 되도록 벽이 설치되어 있다. 이 물탱크를 위에서 내려다보면 <그림 2>와 같이 각 칸이 정사각형인 격자 모양이 된다. 물탱크 각 칸의 벽에는 물 높이 조정을 위해 구멍이 뚫려 있을 수 있다. 각 칸에는 네 개의 벽이 있는데, 각 벽 내부에는 최대 한 개의 구멍이 뚫려 있을 수 있다. 단, 모서리엔 구멍이 없다.

<그림1>

<그림 1>에서 구멍이 있는 높이는 바닥을 기준으로 표시되어 있다. 구멍의 위치를 위에서 보면 <그림 2>처럼 보이는데 이는 물탱크를 위에서 보았을때 어느 벽, 어떤 높이에 구멍이 뚫려 있는지를 알려주며, <그림 1>에선 표시하기 어려운 물탱크의 구멍 위치도 표시한다. <그림 2>에서 보듯이 물탱크 내부 벽에도 구멍이 있을 수 있다.

<그림2>

물탱크에 물을 채울 땐, 모든 구멍을 마개로 막아 물이 새지 못하도록 한 후, 격자의 각 칸 위에 설치된 급수 장치를 통해 물탱크 전체를 물로 채운다. 물이 꽉 찬 후에 구멍을 막고 있는 모든 마개를 제거하면 물이 구멍을 통해 인접한 방이나 외부로 흘러나가게 된다. 어느 정도 시간이 지나면 물이 더 이상 흘러 나가지 않게 되고, 그 때 물탱크 격자의 각 칸에 남아 있는 물의 높이는 서로 다를 수 있다.

참고로, <그림 2>에서 보인 물탱크의 각 칸에 남아 있는 물의 높이를 나타내면 <그림 3>의 괄호 속의 수치와 같다.

<그림3>

벽의 두께를 무시할 때, 물탱크에 남아있는 물의 총량(부피)을 계산하는 프로그램을 작성하시오.

입력

첫 번째줄에는 물탱크의 세로 길이, 가로 길이, 높이를 나타내는 세 양의 정수 N, M, H가 차례로 주어진다.

다음 줄에는 첫 번째 가로 벽에 설치된 구멍 정보를 나타내는 M개의 정수가 주어진다. 각 정수는 왼쪽부터 시작하여 순서대로 각 칸의 구멍 높이를 의미한다. 
구멍의 높이는 0 이상 H미만의 정수이다. 해당 벽에 구멍이 없는 경우는 –1로 표시한다. 

이어지는 줄엔 두 번째 가로 벽에 설치된 구멍 정보가 주어지고, 이런 식으로 N+1줄에 걸쳐 가로 벽에 설치된 모든 구멍에 대한 정보가 주어진다.

이어지는 줄에는 첫 번째 가로 벽을 공유하는 칸들(<그림 2>에서 맨 윗줄의 칸들)의 세로 벽에 설치된 구멍 정보를 나타내는 M+1개의 정수가 주어진다. 각 정수는 첫 번째 세로 벽부터 시작하여 차례로 각 세로 벽의 구멍 높이를 나타낸다. 

그 다음 줄에는 그 다음에 있는 칸들의 세로벽에 설치된 구멍 정보가 주어진다. 
이런 식으로 N 줄에 걸쳐 세로 벽에 설치된 모든 구멍 정보가 주어진다.

참고로, 입출력 예에서 보인 첫 번째 예제는 <그림 2>에서 보인 경우에 대응된다.

 

<부분문제의 제약 조건>

  • 부분문제 1 (6점) : N=1, 1≤M,H≤1,000 이고, 세로 벽에는 구멍이 없다.즉, 물탱크 세로 벽에 대응하는 구멍의 입력은 모두 –1 이다.
  • 부분문제 2 (18점) : N=1, 1≤M,H≤1,000 이다.
  • 부분문제 3 (15점) : H=1,  1≤N,M≤1,000 이다.
  • 부분문제 4 (21점) : 1≤H≤1,000, 1≤N,M≤50  이다.
  • 부분문제 5 (40점) : 1≤N,M,H≤1,000 이다.
출력

물이 더 이상 흘러 나가지 않는 시점에 물탱크에 남아 있는 물의 총량(부피)을 출력한다.

예시
1입력
2 3 5
1 -1 -1
3 2 -1
4 -1 2
-1 -1 4 3
-1 -1 -1 -1
출력
17
2입력
1 5 10
5 -1 -1 -1 6
-1 7 -1 6 -1
-1 2 8 4 2 3
출력
20
출처
2018년 한국정보올림피아드 전국 본선 중등부 3번
위로