Submit | All submissions | Best solutions | Back to list |
V_AYP2_B - Sub-matrix Average |
EspañolDickie 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
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 |
hide comments
2016-12-13 08:27:49 Arpit Gupta
we could have selected the 1X1 matrix containing just 9.. then why is 8.5 the answer?? |