시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 128 MB | 817 | 184 | 117 | 22.117% |
넓은 창고에 상자들을 쌓으려고 한다. 상자는 하나씩 창고에 입고되며, 입고되는 순서대로 쌓아 나가야 한다. 또, 각 상자마다 그 상자를 쌓아야 하는 위치가 정확히 지정되어 있으며, 쌓을 때 회전시킬 수도 없다. 상자들은 직육면체 모양으로, 가로, 세로, 높이의 길이가 다양하다. 상자를 쌓아 둘 창고 역시 직육면체 모양이지만, 그 높이는 충분히 높다고 가정하자.
편의상 창고 바닥의 남서쪽 코너를 원점으로 하여 좌표계를 구성하도록 한다. 창고의 각 모서리는 x, y, z 각 좌표축에 평행하거나 수직하다. x축은 동쪽 방향, y축은 북쪽 방향, z축은 하늘 방향으로 잡는다. 물론 상자들도 각 모서리가 x, y, z축에 평행하거나 수직하게 되도록 쌓을 것이다.
여러분이 할 일은, 주어진 순서대로 각 상자들을 쌓았을 때, 가장 높은 위치의 고도를 알아내는 것이다. 이를 위한 프로그램을 작성하라.
첫 줄에 세 정수 Lx, Ly, N이 주어진다. (1 ≤ Lx, Ly ≤ 1,000, 1 ≤ N ≤ 20,000) Lx와 Ly는 창고의 가로, 세로 길이이며, N은 입고되는 상자의 개수이다. 이후 N개의 줄에 각 상자의 정보가 입고되는 순서로 주어진다. 이는 다섯 개의 정수 lx, ly, lz, px, py 로 이루어진다. (1 ≤ lx, 0 ≤ px, px+lx ≤ Lx, 1 ≤ ly, 0 ≤ py, py+ly ≤ Ly, 1 ≤ lz ≤ 100,000) lx, ly, lz는 각각 상자의 가로, 세로, 높이 길이를 나타낸다. px, py는 상자를 쌓아야 하는 위치를 나타낸다. 상자 바닥의 네 꼭짓점 중 가장 남서쪽에 있는 것의 x, y좌표를 px, py에 맞추어 쌓으면 된다.
첫 줄에 상자를 모두 쌓았을 때, 가장 높은 곳의 고도를 출력한다.
7 5 4 4 3 2 0 0 3 3 1 3 0 7 1 2 0 3 2 3 3 2 2
6
네 개의 상자를 순서대로 모두 쌓고 난 뒤, 각 상자의 꼭짓점 좌표는 다음과 같다.
Olympiad > Polish Olympiad in Informatics > POI 2005/2006 > Stage 1 4번