1 #include<cstdio> 2  3 #include<cstdlib> 4  5 #include<cmath> 6  7 #include<cstring> 8  9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 1126 27 #define maxm 200000+528 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)44 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)46 47 #define mod 100000000748 #define sqr(x) (x)*(x)49 50 using namespace std;51 52 inline int read()53 54 {55 56     int x=0,f=1;char ch=getchar();57 58     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}59 60     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}61 62     return x*f;63 64 }65 int n,m,k,s[maxn][maxn];66 double ave,f[maxn][maxn][maxn][maxn][maxn];67 inline double dp(int x1,int y1,int x2,int y2,int z)68 {69     double &t=f[x1][y1][x2][y2][z];70     if(t<inf)return t;71     if(!z)return t=sqr(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]-ave);72     t=inf;73     for0(i,z-1)74      {75          for2(j,x1,x2-1)t=min(t,dp(x1,y1,j,y2,i)+dp(j+1,y1,x2,y2,z-1-i));76          for2(j,y1,y2-1)t=min(t,dp(x1,y1,x2,j,i)+dp(x1,j+1,x2,y2,z-1-i));77      }78     //cout<<x1<<‘ ‘<<y1<<‘ ‘<<x2<<‘ ‘<<y2<<‘ ‘<<z<<‘ ‘<<t<<endl;79     return t;80 }81 82 int main()83 84 {85 86     freopen("input.txt","r",stdin);87 88     freopen("output.txt","w",stdout);89 90     n=read();m=read();k=read();91     for1(i,n)for1(j,m)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+read();92     ave=(double)s[n][m]/(double)k;93     for1(i1,n)for1(i2,m)for1(i3,n)for1(i4,m)for0(i5,k)f[i1][i2][i3][i4][i5]=inf;94     dp(1,1,n,m,k-1);95     printf("%.2f\n",sqrt((double)f[1][1][n][m][k-1]/(double)k));96 97     return 0;98 99 }