DMOPC '15 Contest 4 P6 - Alarms

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

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 N\times N matrix, with a cell containing 1 representing an empty room, and 0 representing a wall. Your task is to place exactly A alarms in the building so that the essays are maximally safeguarded. Each alarm i has a square range of R\_i 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?

Input Specification

The first line of input will contain the integer N (1 \le N \le 6).
The next N lines will each contain N space-separated integers, representing one row of the Archives.
The next line of input will contain the integer A (1 \le A \le 6).
The final line of input will contain A space-separated integers, with the i-th integer denoting R\_i (1 \le R\_i \le 3).

Output Specification

A single integer; the maximum number of rooms that may be covered by alarms.

Sample Input

0 1 1 0
0 1 1 1
1 1 1 1
1 1 1 0
1 2 1 1

Sample Output



You can place the radius 2 alarm at (1,2), and two radius 1 alarms at (2, 0) and (3, 1) for a coverage of 10. You are left with one more alarm, but you cannot cover any more rooms without placing multiple alarms on the same row or column.


There are no comments at the moment.