记录编号	368380	评测结果	AAAAAAAAAA
题目名称	[HAOI 2007]理想的正方形	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.703 s
提交时间	2017-02-05 00:10:57	内存使用	76.17 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <queue>
#include <vector>
#include <string>
#include <cctype>
#include <algorithm>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;}
  inline int readint(){
    char c; int r; bool s = false;
    while(c = readc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
  }
}; using IO::readint;
struct mminfo{
  int maxv, minv;
};
mminfo f[1001][1001][11];
inline int max4(int a, int b, int c, int d){
  return max(a, max(b, max(c, d))); 
}
inline int min4(int a, int b, int c, int d){
  return min(a, min(b, min(c, d)));
}
int main(){
 // freopen("test_data.txt", "r", stdin);
  freopen("square.in", "r", stdin);
  freopen("square.out", "w", stdout);
  int a, b, n;
  a = readint(); b = readint(); n = readint();
  for(int i = 0; i < a; i++)for(int j = 0; j < b; j++)
    f[i][j][0].maxv = f[i][j][0].minv = readint();
  for(int k = 1; (1<<k) <= n; k++)
    for(int i = 0; i+(1<<k)-1 < a; i++)
      for(int j = 0; j+(1<<k)-1 < b; j++){
        f[i][j][k].maxv = max4(f[i][j][k-1].maxv, f[i+(1<<(k-1))][j][k-1].maxv, 
                f[i][j+(1<<(k-1))][k-1].maxv, f[i+(1<<(k-1))][j+(1<<(k-1))][k-1].maxv);
        f[i][j][k].minv = min4(f[i][j][k-1].minv, f[i+(1<<(k-1))][j][k-1].minv,
                f[i][j+(1<<(k-1))][k-1].minv, f[i+(1<<(k-1))][j+(1<<(k-1))][k-1].minv);
      }
  int s = 0;while((1<<s) <= n)s++; s--;
  int t = n-(1<<s);
  int ans = 0x7fffffff;
  for(int i = 0; i+n-1 < a; i++)
    for(int j = 0; j+n-1 < b; j++)
    {
      int maxv = max4(f[i][j][s].maxv, f[i+t][j][s].maxv, f[i][j+t][s].maxv, f[i+t][j+t][s].maxv);
      int minv = min4(f[i][j][s].minv, f[i+t][j][s].minv, f[i][j+t][s].minv, f[i+t][j+t][s].minv); 
      ans = min(ans, maxv-minv);
    }
  printf("%d\n", ans);
  return 0;
}