Practice on Toph

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

Land of Riches

By Peregrine_Falcon · Limits 1s, 512 MB

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 NN rows and MM columns numbered from 11 to NN and 11 to MM. Cells can be represented with XX and YY. XX stands for the row and YY stands for the column. Each cell contains WXYW_{XY} unit of wealth. Value of WXYW_{XY} equal to 00 means empty cell.

CC 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 2424 hours and 3737 minutes(60 minutes per hour). The army of ithi^{th} country will land on cell XiX_i YiY_i. The time of landing will be given to you in format hh:mmhh: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 ii 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 NN and MM (3N,M500)(3 \leq N, M \leq 500).
Each of the next NN lines will contain MM integers WW (0W100)(0 \leq W \leq 100 ) representing the wealth of the cell.
The next line will contain integer CC (1CN×M)(1 \leq C \leq N \times M).
CC line follows. ithi^{th} line will contain the time of landing for the ithi_{th} army in the format hhi:mmihh_i : mm_i(00:00hhi:mmi24:36)(00:00 \leq hh_i:mm_i \leq 24:36) and the cell Xi,YiX_i, Y_i (1XiN,1YiM)(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 TT that can be collected by the armies of the earth.
For the next CC lines, print one integer each. In the ithi_{th} line, print the total amount of wealth will be collected by the ithi_{th} army.


4 4
1 2 1 2
0 3 0 5
0 1 7 4
10 0 5 3
00:22 4 1
24:36 1 4
24:36 3 2

At 00:2200:22, the first army will land on the cell 4,14,1 and collect 1010 units.
At 24:3624:36, the 2nd2_{nd} army will land on cell 1,41,4 and collect 2 units. At the same time the 3rd3_{rd} army will land on cell 3,23,2 and collect 11 unit.
Next day, at 00:0000:00 the 2nd2_{nd} army will spread to cells 1,31,3 and 2,42,4. They will collect 11 and 55 units respectively. At the same time, the 3rd3_{rd} army will spread to cells 2,22,2 and 3,33,3. They will collect 33 and 77 units.
At 00:0100:01 both army can occupy the cells 1,21,2 and 3,43,4. But the 2nd2_{nd} army will occupy them because of lower ii value and they will collect 22 and 44 from these cells. At the same time, the 3rd3_{rd} army will occupy cell 4,34,3 and collect 55 units.
At 00:0200:02 the 2nd2_{nd} army will occupy cells 1,11,1 and 4,44,4. They will collect 11 and 33 units from there.

All the armies combined will collect 4444 units of wealth. The first, second, and third armies will collect 1010,1818 and 1616 units respectively.



71% Solution Ratio

tanvirtareqEarliest, 2M ago

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 ...

Related Contests

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