물 탱크 |
---|
세로 길이가 NN, 가로 길이가 MM, 높이가 HH인 물탱크가 있다. NN, MM, HH는 모두 양의 정수이다. <그림 1>은 세로 길이가 22, 가로 길이가 33, 높이가 55인 물탱크 모양을 보여준다. <그림 1>에서 보듯이 물탱크 내부는 가로와 세로로 벽이 설치되어 있는데, 내부 각 칸(즉 사각기둥 모양)의 세로와 가로 길이는 1이고 높이는 H가 되도록 벽이 설치되어 있다. 이 물탱크를 위에서 내려다보면 <그림 2>와 같이 각 칸이 정사각형인 격자 모양이 된다. 물탱크 각 칸의 벽에는 물 높이 조정을 위해 구멍이 뚫려 있을 수 있다. 각 칸에는 네 개의 벽이 있는데, 각 벽 내부에는 최대 한 개의 구멍이 뚫려 있을 수 있다. 단, 모서리엔 구멍이 없다. <그림 1>에서 구멍이 있는 높이는 바닥을 기준으로 표시되어 있다. 구멍의 위치를 위에서 보면 <그림 2>처럼 보이는데 이는 물탱크를 위에서 보았을때 어느 벽, 어떤 높이에 구멍이 뚫려 있는지를 알려주며, <그림 1>에선 표시하기 어려운 물탱크의 구멍 위치도 표시한다. <그림 2>에서 보듯이 물탱크 내부 벽에도 구멍이 있을 수 있다. 물탱크에 물을 채울 땐, 모든 구멍을 마개로 막아 물이 새지 못하도록 한 후, 격자의 각 칸 위에 설치된 급수 장치를 통해 물탱크 전체를 물로 채운다. 물이 꽉 찬 후에 구멍을 막고 있는 모든 마개를 제거하면 물이 구멍을 통해 인접한 방이나 외부로 흘러나가게 된다. 어느 정도 시간이 지나면 물이 더 이상 흘러 나가지 않게 되고, 그 때 물탱크 격자의 각 칸에 남아 있는 물의 높이는 서로 다를 수 있다. 참고로, <그림 2>에서 보인 물탱크의 각 칸에 남아 있는 물의 높이를 나타내면 <그림 3>의 괄호 속의 수치와 같다. 벽의 두께를 무시할 때, 물탱크에 남아있는 물의 총량(부피)을 계산하는 프로그램을 작성하시오. |
입력 | |
---|---|
첫 번째줄에는 물탱크의 세로 길이, 가로 길이, 높이를 나타내는 세 양의 정수 N, M, H가 차례로 주어진다. 이어지는 줄엔 두 번째 가로 벽에 설치된 구멍 정보가 주어지고, 이런 식으로 N+1줄에 걸쳐 가로 벽에 설치된 모든 구멍에 대한 정보가 주어진다. 이어지는 줄에는 첫 번째 가로 벽을 공유하는 칸들(<그림 2>에서 맨 윗줄의 칸들)의 세로 벽에 설치된 구멍 정보를 나타내는 M+1개의 정수가 주어진다. 각 정수는 첫 번째 세로 벽부터 시작하여 차례로 각 세로 벽의 구멍 높이를 나타낸다. 그 다음 줄에는 그 다음에 있는 칸들의 세로벽에 설치된 구멍 정보가 주어진다.
<부분문제의 제약 조건>
|
출력 | |
---|---|
물이 더 이상 흘러 나가지 않는 시점에 물탱크에 남아 있는 물의 총량(부피)을 출력한다. |
예시 | |||
---|---|---|---|
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번 |