LYDSY 1047
题目大意
暂无
题目解法
暂无
RTFC
#include <cctype>
#include <cstdio>
#include <cstring>
inline int min(int a, int b) { return a < b ? a : b; }
inline void readInt(int &x)
{
int ch = x = 0;
while (!isdigit(ch = getchar()))
;
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
int mat[1001][1001], maxn[1001][1001], minn[1001][1001], a, b, n;
struct MQueue
{
int head, tail, que[1001][2];
MQueue() : head(0), tail(0) {}
void insert(int x, int pos)
{
while (head < tail && que[tail - 1][0] < x) tail--;
que[tail][0] = x, que[tail][1] = pos;
tail++;
while (head < tail && pos - que[head][1] >= n) head++;
}
int top() const { return que[head][0]; }
} MQ[1001];
void gen(int f[1001][1001])
{
memset(MQ, 0, sizeof(MQ));
for (int i = 0; i < a; i++)
for (int j = 0; j < n - 1; j++)
MQ[i].insert(mat[i][j], j);
;
for (int j = n - 1; j < b; j++)
{
for (int i = 0; i < a; i++)
MQ[i].insert(mat[i][j], j);
MQueue q;
for (int i = 0; i < n - 1; i++)
q.insert(MQ[i].top(), i);
for (int i = n - 1; i < a; i++)
q.insert(MQ[i].top(), i),
f[i][j] = q.top();
}
}
int main()
{
readInt(a), readInt(b), readInt(n);
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
readInt(mat[i][j]);
gen(maxn);
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
mat[i][j] = -mat[i][j];
gen(minn);
int ans = 0x3f3f3f3f;
for (int i = n - 1; i < a; i++)
for (int j = n - 1; j < b; j++)
ans = min(ans, maxn[i][j] - -minn[i][j]);
printf("%d", ans);
return 0;
}