记录编号 | 115277 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [HAOI 2007]理想的正方形 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | C++ | 运行时间 | 1.107 s | ||
提交时间 | 2014-08-16 17:44:54 | 内存使用 | 11.98 MiB | ||
#include <cstdio> #include <climits> #include <deque> using namespace std; int n,m,k,i,j,a[1010][1010],mi[1010][1010],ma[1010][1010],ans=INT_MAX; deque <int> qi,qd; int main() { freopen("square.in","r",stdin); freopen("square.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for (i=1;i<=n;++i) for (j=1;j<=m;++j) scanf("%d",&a[i][j]); for (i=1;i<=n;++i) { while (!qi.empty()) qi.pop_back(); while (!qd.empty()) qd.pop_back(); for (j=1;j<=m;++j) { while (!qi.empty()&&a[i][j]<=a[i][qi.back()]) qi.pop_back(); while (!qd.empty()&&a[i][j]>=a[i][qd.back()]) qd.pop_back(); qi.push_back(j); qd.push_back(j); if (j>=k) { if (j-qi.front()>=k) qi.pop_front(); else if (j-qd.front()>=k) qd.pop_front(); mi[i][j]=a[i][qi.front()]; ma[i][j]=a[i][qd.front()]; } } } for (j=k;j<=m;++j) { while (!qi.empty()) qi.pop_back(); while (!qd.empty()) qd.pop_back(); for (i=1;i<=n;++i) { while (!qi.empty()&&mi[i][j]<=mi[qi.back()][j]) qi.pop_back(); while (!qd.empty()&&ma[i][j]>=ma[qd.back()][j]) qd.pop_back(); qi.push_back(i); qd.push_back(i); if (i>=k) { if (i-qi.front()>=k) qi.pop_front(); else if (i-qd.front()>=k) qd.pop_front(); ans=min(ans,ma[qd.front()][j]-mi[qi.front()][j]); } } } printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; }