V_AYP2_B - Sub-matrix Average

no tags 

Español

Dickie is learning the utilities of a matrix in the school, then the professor asked him to find the maximum submatrix in a matrix given, so that the average is maximum, we define the average in a submatrix as the sum between all the elements on the submatrix divided by the number of cells evaluating, so for example.

 

3 2 3

4 9 8

1 8 9

 

The example matrix has 4 submatrix, these are { {0,0,1,1}. {0,1,1,2}, {1,0,2,1}, {1,1,2,2} } (The values given are the pair (row,column) for the leftmost top corner and the rightmost bottom corner), of course, the maximum average obtainable in this example is the last one, giving ( (9+8+9+8) / 4 → 34 / 4 → ) 8.50

 

For simplicity, we ask you to print the result with two decimal places, i.e. instead of printing 8.5 you should print 8.50, if there is any result with more than two, round it up, i.e. if the result is 8.66666... you should print 8.67.

 

Input details:

You must read two integers N and M, representing, respectively, the matrix N and the submatrix M to take, after that, N lines with N integers separated by a space will come, each representing the position in the matrix.

 

Output details:

You should print the maximum average obtainable having in count that you should always form a submatrix of MxM in the bigger matrix N.

 

INPUT

OUTPUT

3 2

1 5 3

9 9 8

7 8 9

8.50

 

Constraints:

1 <= N <= 20

1 <= M <= N


hide comments
Arpit Gupta: 2016-12-13 08:27:49

we could have selected the 1X1 matrix containing just 9.. then why is 8.5 the answer??


Added by:Venezuelan Programming League
Date:2013-02-02
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64