Woburn Challenge 2015-16 Round 3 - Senior Division

Problem 3: Rescue Mission

While the dust settles in the battle between the dark knight and the last son of Krypton, the two have suddenly come to recognize the true mastermind behind it all. After General Zod's invasion on Earth, LexCorp was contracted by the U.S. government to carefully reverse-engineer leftover Kryptonian technology. As it turns out, the battle between the heroes had simply been Lex Luthor's test in his greater conspiracy to craft a powerful biotechnological weapon against Superman. At that point, it became clear to both that the world is in much graver danger than ever before. Now, the heroes have decided to team up and together, track down Luthor to end the evil mastermind's ploys once and for all.

They have tracked down Luthor's activities preceding their fight to Cadmus, a LexCorp subsidiary dedicated to genetic research on the outskirts of Metropolis. Unbeknownst to even the government, Cadmus has been conducting dangerous human experimentation for a secret biotechnology project. Infiltrating the facility, the heroes have discovered a huge number of human subjects that are held prisoner by Luthor. As they plan to secretly rescue all of them, Lex has already discovered their presence. Immediately, he sets his men, armed with advanced weaponry, into action to capture Batman and Superman. With a limited amount of time before they can escape, the duo must try to rescue as many prisoners as possible.

The Cadmus facility can be represented as a rectangular grid with N rows of M cells each (2 ≤ N, M ≤ 2000), with the rows numbered 1..N from north to south, and the columns numbered 1..M from west to east. The j-th cell in the i-th row can be denoted as cell (i, j). Each cell (i, j) happens to contain P_{i, j} (0 ≤ P_{i, j} ≤ 10⁵) prisoners. Batman and Superman must work together to rescue as many as they can – but with the clock ticking, they have to make their rescue plan as efficient as possible.

Thus, Batman and Superman will each decide on their own "rescue zone". Each rescue zone is defined by a central point (r, c), a non-negative height h, and a non-negative width w. A rescue zone consists of h + w + 1 cells – the central cell itself, the h cells directly above it, and the w cells directly to the left of it. This zone is only valid if all of its cells are within the grid – that is, 0 ≤ h < r ≤ N and 0 ≤ w < c ≤ M must hold true. However, to avoid getting in each other's way, their chosen rescue zones should not overlap with one another. In other words, no cell in the Cadmus facility may be part of both rescue zones. Following this, all prisoners in each cell which are either part of Batman or Superman's attack zones will be rescued.

Please write a program to help the Earth's greatest heroes determine the maximum number of prisoners that can be rescued this way.

Input Format

The first line contains two space-separated integers N and M.
The next N lines each contain M integers, where line i contains integers P_i,1, …, P_i,M, for i = 1..N.

Output Format

Output a single integer, the maximum number of prisoners that can be rescued by Batman and Superman.

Sample Input

4 6
2 0 3 0 0 0
0 0 0 0 4 0
0 1 1 2 0 0
2 0 3 0 0 1

Sample Output

15

Explanation

One optimal pair of rescue zones is as follows:

• r = 3, c = 5, h = 1, w = 1 (containing 4 + 2 = 6 prisoners)
• r = 4, c = 3, h = 3, w = 2 (containing 3 + 1 + 3 + 2 = 9 prisoners)

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 256M
Added: Feb 13, 2016
Authors: SourSpinach, Alex

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

Comments (Search)