Maximum Average Submatrix

題目敘述

給你一個n行m列的矩陣，請輸出最大平均子矩陣的平均值，到小數點後第k位，超過k位則四捨五入

這裡的子矩陣(Submatrix)的定義為:

從原來的矩陣\(M\)中取出一塊\(p*q\)的區域(\(p,q\)可為0)，稱之為\(M\)的子矩陣，和線性代數的定義不一樣

請參考這裡

子矩陣的平均值的意思就是假設現在有一個\(p*q\)的子矩陣，其數值總合為\(sum\)，則其平均值為\(sum/(p*q)\)
我們目標就是要找平均值最大的子矩陣

輸入說明

第一行會有三個數字n,m,k，表示矩陣的大小及輸出要到小數點後第k位，其中\(1 \leq\)n,m\(\leq 10^3\)，\(0 \leq\)k\(\leq 12\)，接下來會有n行，每行有m個整數(int範圍)，表示矩陣。

輸出說明

輸出一個浮點數，要到小數點後第k位，超過k位則四捨五入，表示最大平均子矩陣的平均值

詳請見範例輸入輸出

範例輸入 1

2 3 1
5 2 -3
5 5 5

範例輸出 1

5.0

範例輸入 2

2 3 4
-99 -10 -11
-6 -8 -9

範例輸出 2

0.0000

配分方法

• 10% 範例測資
• 20% n,m\(\leq 10\)
• 30% n,m\(\leq 100\)
• 40% 不限

Hints

備註

Judge Setting