Square Maze

Saadmaan007 Father Timm Memorial Prog...
Limits 1.5s, 256 MB

Sajib is a criminal. Respected judge has sentenced him to prison for 10 years! He is now spending his lazy time in prison.

You are also trapped inside the prison with Sajib. Bored Sajib started playing with a rectangular grid of dimension NMN * M where each element can be either an integer between 0 or 1. Sajib wants to find out the maximal area of a square consisting of only 1's from the rectangular grid. But there is a catch!

There are some special cells in the grid. Sajib knows there are exactly KK of them in the rectangular grid. He knows their positions as well. One can toggle the value of such cells from 0 to 1 or from 1 to 0 if they want, as many times as they wish! The cost of toggling ithi_{th} special cell is given by CiC_i.

As Sajib is not a programmer (and you are), can you help him find out the maximal area of a square consisting of only 1's with minimum cost of toggling?


The first line of the input contains an integer TT (1T71 ≤ T ≤ 7), number of test cases.

The second line of each input contains three integers NN, MM (1N,M,C10001 ≤ N,M,C ≤ 1000), and KK (0Kmin(N×M,104)0 ≤ K ≤ min(N \times M, 10^4)) denoting the number of rows, columns, and special cells respectively.

In the next NN lines, there will be MM space-separated integers.

After that, there will be KK lines for each test case. In each line, there will be three integers denoting the position (row and column) of the special cells and the CiC_i (1Ci10001 ≤ C_i ≤ 1000) cost of toggling the cell. All the indices will be 0-based.


Print the desired maximal area and the minimum cost (space-separated) in a single line for each test case.


3 3 0
0 1 0
0 1 1
1 1 1
4 0

Large data set. Use faster I/O.

If there are multiple maximal squares satisfying all the conditions, you need to choose the one with minimum cost.


Login to submit.


50% Solution Ratio
Tahmid690Earliest, Oct '20
Nasif_44thFastest, 0.3s
fsshakkhorLightest, 16 MB
Kabir03Shortest, 2243B
Toph uses cookies. By continuing you agree to our Cookie Policy.