Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Mankind has recently discovered the secret wealth in Mars. Many powerful countries are trying to get hold of the riches of Mars. The map of Mars can be represented as a 2-Dimensional grid consisting of $N$ rows and $M$ columns numbered from $1$ to $N$ and $1$ to $M$. Cells can be represented with $X$ and $Y$. $X$ stands for the row and $Y$ stands for the column. Each cell contains $W_{XY}$ unit of wealth. Value of $W_{XY}$ equal to $0$ means empty cell.

$C$ countries are preparing their armies to collect as much wealth as they can. All the countries will land their armies on the same day. One day on Mars contains $24$ hours and $37$ minutes(60 minutes per hour). The army of $i^{th}$ country will land on cell $X_i$ $Y_i$. The time of landing will be given to you in format $hh:mm$. After landing on a cell, if there is any wealth in the cell they will immediately collect them. Otherwise, they will not continue their operation and return empty-handed. The time of collecting wealth is negligible. After collecting the wealth, the army will split and expand to the adjacent cells vertically and horizontally if there is any wealth in those cells. This process will be continued from each cell. If two armies try to advance in the same cell at the same time, the army with a smaller value of $i$ will get hold of the cell. Moving from one cell to another takes exactly one minute.

You have to calculate, how much wealth all the armies can collect and which army can collect how much wealth.

The first line of input will consist of two integers $N$ and $M$ $(3 \leq N, M \leq 500)$.

Each of the next $N$ lines will contain $M$ integers $W$ $(0 \leq W \leq 100 )$ representing the wealth of the cell.

The next line will contain integer $C$ $(1 \leq C \leq N \times M)$.

$C$ line follows. $i^{th}$ line will contain the time of landing for the $i_{th}$ army in the format $hh_i : mm_i$$(00:00 \leq hh_i:mm_i \leq 24:36)$ and the cell $X_i, Y_i$ $(1 \leq X_i \leq N, 1 \leq Y_i \leq M)$ the army will land.

In the first line print the total units of wealth $T$ that can be collected by the armies of the earth.

For the next $C$ lines, print one integer each. In the $i_{th}$ line, print the total amount of wealth will be collected by the $i_{th}$ army.

Input | Output |
---|---|

4 4 1 2 1 2 0 3 0 5 0 1 7 4 10 0 5 3 3 00:22 4 1 24:36 1 4 24:36 3 2 | 44 10 18 16 |

At $00:22$, the first army will land on the cell $4,1$ and collect $10$ units. All the armies combined will collect $44$ units of wealth. The first, second, and third armies will collect $10$,$18$ and $16$ units respectively. |

71% Solution Ratio

tanvirtareqEarliest,

fextivityFastest, 0.1s

fextivityLightest, 11 MB

tanvirtareqShortest, 1155B

Login to submit

This problem can be solved by the Dijkstra algorithm. Ring any bells? What will be the priority for ...

Toph uses cookies. By continuing you agree to our Cookie Policy.