AIOC Banner

Problem: Art, Key, Texture

Want to try solving this problem? You can submit your code online if you log in or register.


Art, Key, Texture

Time Limit: 1.5 seconds
Memory Limit: 128 MB
Input: stdin
Output: stdout

You are Michelangelo, a budding artist in Renaissance Italy who has been employed by a wealthy noble to create the most beautiful sculpture in all the lands.

You begin with an upright marble slab which can be thought of as a H  x  W grid of 1  x  1 marble blocks. You then chisel away unnecessary parts of the slab until you are left with a beautiful sculpture consisting of zero or more blocks.


It is key that:

\includegraphics[width=13cm]{arch}

Unfortunately, your creative desires are stifled by commercial constraints: the noble you are making this sculpture for has a particular distaste for the some of your slab's marble blocks (the textures are too "swirly", you're told), and a particular penchant for others ("Yes! I like those colours"). For each marble block you have a number - possibly negative - indicating how beautiful it is. Your task is to design a sculpture where the sum of these "beauty numbers" is as large as possible.

Input

Output

Output should consist of a single integer: the largest possible sum of "beauty numbers" for your sculpture.

Sample Input 1

5 6
-99 1 -99 -99 1 -99
1 -99 1 1 -99 1
-99 1 -99 1 1 -99
1 1 -99 1 1 1
1 1 1 1 -99 1

Sample Output 1

7

Sample Input 2

5 4
7 1 1 2
-5 2 -6 3
-3 -8 1 -4
4 2 -2 -3
-1 3 1 1

Sample Output 2

10

Explanation

Below are possible sculptures that maximise the sum of "beauty numbers" for each sample case above.

\includegraphics[width=13cm]{pyramid_sample}

Subtasks & Constraints

For all subtasks, 1 ≤ H, W ≤ 1,000 and all "beauty numbers" are integers between -1,000,000 and 1,000,000 inclusive.

 


Privacy statement
© Australian Mathematics Trust 2001-2021

Contact: training@orac.amt.edu.au
Page generated:  1 December 2021, 11:34am AEDT