TETRIS3D - Tetris 3D

题意翻译

# 题目描述 “俄罗斯方块”的作者决定制作一个3D版本的“俄罗斯方块”。有若干个长方体积木,它们将以一定的顺序下落,最底端是一个矩形平台。积木停止下落当且仅当它碰到了矩形平台或另一个已经停止下落的积木。它将保持这个位置不变直至游戏结束。 然而作者想要改变这个游戏的玩法。已知积木的下降顺序以及积木的起始释放位置,求游戏结束后积木堆最高点的高度。假设积木竖直下落且不旋转。为了描述方便起见,我们引入一个笛卡尔坐标系,原点为平台的顶点,轴与平台边缘平行。 # 输入格式 第一行有3个整数$D,S,N$,分别代表矩形平台的长、宽和积木数。其中$1\leq N \leq 20000,1\leq D,S\leq 1000$。 接下来$N$行,每行5个整数$d,s,w,x,y$描述了 一个积木。$1\leq d,s$,$1\leq w \leq 100000$,$0\leq x,d+x\leq D$, $0\leq y,s+y\leq S$。 数据说明这个积木的长宽高分别为$d,s,w$,且顶点在平台上的投影坐标为$(x,y),(x+d,y),(x,y+s),(x+d,y+s)$。 # 输出格式 仅1行1个整数,即积木堆最高点高度。

题目描述

The authors of the game "Tetris" have decided to make a new, three-dimensional version, in which cuboids would fall down on a rectangular platform. The blocks fall down separately in a certain order, just like in the two-dimensional game. A block falls down until it reaches an obstacle: the platform or another block, that has already stopped - then it stops and remains in this exact position till the game is over. However, the authors wanted to change the spirit of the game, turning it from a simple arcade-game into a play far more puzzling. Knowing the order of the falling blocks and their flight path the player's task is to tell the height of the highest point of the arrangement after all blocks have fallen down (and stopped). All the blocks are falling down vertically and do not rotate while falling. For convenience we'll introduce a cartesian coordinate system on the platform, with the center in one of the platform's corners and the axes parallel to the platform's edges. Write a program that: • reads the descriptions of subsequent falling blocks from the standard input, • determines the height of the highest point of the arrangement of blocks after all have fallen down and stopped, • writes the result to the standard output.

输入输出格式

输入格式


In the first line of the input there are three integers D, S and N ( 1<=N<=20 000, 1<=D, S<=1 000), separated by single spaces and denoting respectively: the length and the depth of the platform and the number of blocks that are going to fall down on it. In the following N lines the descriptions of subsequent blocks are given, one in each line. Each description of a block consists of five integers: d, s, w, x and y (1<=d, 0<=x,d+x<=D, 1<=s,0<=y,s+y<=S, 1<=w<=100 000), representing a block of length d depth s and height w This very block will be falling down on the platform with its d×s face as the bottom, where the length and depth of the block are parallel to those of the platform. The coordinates of the vertices of the projection of the block on the platform are: (x, y), (x + d, y), (x, y + s) and (x + d, y + s).

输出格式


The first and only line of the standard output should contain exactly one integer, the height of the highest point of the arrangement of blocks after all have fallen down ad stopped.

输入输出样例

输入样例 #1

7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2

输出样例 #1

6