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.

Input

Output

For each test case, output the amount of juice the given bowl can hold.

Sample Input

1
4 4
4 4 4 4
4 1 1 4
4 1 1 4
4 4 4 4

Sample Output

12

All Submissions
Best Solutions

Point Value: 25
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Some of the heights of the bowl can be 0 - however, this doesn't mean that there's a hole in the bowl! A height of 0 is simply lower than a height of 1.

Sorry, but you shouldn't get 25 points for solutions that don't work :(

How do you choose whether or not a problem deserves partial points?

For this problem, if you have the correct idea (and no bugs) you will get full points. It's one of those "you get it or you don't" things. There is no need for partial marks, and doing so would just encourage solutions that don't really work. (Especially since this is a 25 pt problem)

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.

Does the funky punch-bowl have more than 1 space between the boxes?
eg.
1
3 5
5 5 5 5 5
5 4 5 1 3
5 5 5 5 5

Sure, why not?