【题解】
n^6的做法很好想，然而这样复杂度不对。。
然后我们可以发现R和C可以分开求，这样复杂度降到了n^4. 使用树状数组可以把复杂度降到n^3logn，可以顺利通过。
1 #include<cstdio> 2 #include<algorithm> 3 #define N 1010 4 #define rg register 5 #define lowbit (x&-x) 6 using namespace std; 7 int n,m,r,c,ans,a[N][N],b[N],t[N]; 8 inline int read(){ 9 int k=0,f=1; char c=getchar(); 10 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 11 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 12 return k*f; 13 } 14 inline void add(int x,int y){ 15 for(;x<=n;x+=lowbit) t[x]+=y; 16 } 17 inline int query(int x){ 18 int ret=0; for(;x;x-=lowbit) ret+=t[x]; return ret; 19 } 20 inline bool check1(int len){ 21 for(rg int j=1;j<=n;j++){ 22 for(rg int i=1;i<=m;i++) b[i]=a[j][i]; 23 for(rg int i=1;i<=m-len+1;i++){ 24 if(b[i]<0) return 0; 25 for(rg int k=i+1;k<=i+len-1;k++) b[k]-=b[i]; b[i]=0; 26 } 27 for(rg int i=m-len+2;i<=m;i++) if(b[i]!=0) return 0; 28 // for(rg int i=1;i<=m;i++) printf("%d ",b[i]); puts(""); 29 } 30 return 1; 31 } 32 inline bool check2(int len){ 33 for(rg int j=1;j<=m;j++){ 34 for(rg int i=1;i<=n;i++) b[i]=a[i][j]; 35 for(rg int i=1;i<=n-len+1;i++){ 36 if(b[i]<0) return 0; 37 for(rg int k=i+1;k<=i+len-1;k++) b[k]-=b[i]; b[i]=0; 38 } 39 for(rg int i=n-len+2;i<=n;i++) if(b[i]!=0) return 0; 40 // for(rg int i=1;i<=m;i++) printf("%d ",b[i]); puts(""); 41 } 42 return 1; 43 } 44 int main(){ 45 n=read(); m=read(); 46 for(rg int i=1;i<=n;i++) 47 for(rg int j=1;j<=m;j++) a[i][j]=read(),ans+=a[i][j]; 48 for(rg int i=m;i>=1;i--) if(check1(i)){ 49 c=i; break; 50 } 51 for(rg int i=n;i>=1;i--) if(check2(i)){ 52 r=i; break; 53 } 54 printf("%d ",ans/r/c); 55 return 0; 56 }