Woburn Challenge 1999 - Suicidal
The Wedding Juicer
Adam Sandler is now a wedding juicer, i.e. he designs interesting punch-bowl designs. His latest design is as follows: it is built up from a flat board of dimensions nxm (m,n ≤ 100). Onto the board, he pastes nxm solid blocks - each 1x1 in width, but with variable heights (height will be integers ≤ 10000), i.e. the entire board is covered with these blocks and no 2 blocks are stacked. To determine if this is a feasible design for a wedding, he needs to determine how much punch can fit into this funky punchbowl. So, you might wonder where the juice is going to go if all the blocks are solid. Keep in mind that juice can get trapped between boxes.
You will be given n and m, followed by a grid of n rows of m items (each item separated by ONE space). This grid will contain the heights of the cuboid block at that grid position on the board. Given these numbers, you must output the volume of punch that will fit into the bowl. Assume that there is no surface tension on the board and so an unbounded region can hold no juice.
InputLine 1: Number of input sets
Each input set has the following format:
- 1st line: n m, the height and width of the board
- n lines each containing m positive integers, representing the height of the squares of the bowl
For each test case, output the amount of juice the given bowl can hold.
1 4 4 4 4 4 4 4 1 1 4 4 1 1 4 4 4 4 4
Point Value: 25
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
For some problems, like Daycare, you get partial marks because there is also the question of efficiency - you can make a correct but slow algorithm. Thus you'll get some points for this, but making it faster is quite difficult, and hence worth more points.
5 5 5 5 5
5 4 5 1 3
5 5 5 5 5