DMOPC '15 Contest 4 P6 - Alarms
Library and Archives Canada recently decided to install an alarm system to safeguard the English essays of past generations, and they've hired you to help them.
The Archives may be represented by an matrix, with a cell containing
1 representing an empty room, and
0 representing a wall. Your task is to place exactly alarms in the building so that the essays are maximally safeguarded. Each alarm has a square range of units around its radius, and you're interested in covering a maximum number of rooms.
There are a couple of restrictions:
- no alarm may be placed in a wall
- you may only place one alarm per column or row
- an alarm's range cannot overlap with the outside of the building
- alarm ranges can overlap
Knowing this, what is the maximum number of rooms you can hope to secure?
The first line of input will contain the integer .
The next lines will each contain space-separated integers, representing one row of the Archives.
The next line of input will contain the integer .
The final line of input will contain space-separated integers, with the -th integer denoting .
A single integer; the maximum number of rooms that may be covered by alarms.
4 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 4 1 2 1 1
You can place the radius alarm at , and two radius alarms at and for a coverage of . You are left with one more alarm, but you cannot cover any more rooms without placing multiple alarms on the same row or column.