0分求条

#include <bits/stdc++.h>

using namespace std;

int a, b, n, c[1001][1001], q[1001], front = 1, rear = 0, Min[1001][1001], Max[1001][1001], len1, len2;
int tmp1[1001], tmp2[1001], p[1001], r[1001];

void work1(int c[], int d[], int l) {
	front = 1, rear = 0;
	len1 = 0;
	for (int i = 1; i <= l; i++) {
		while (front <= rear && c[q[rear]] >= c[i])
			rear--;
		q[++rear] = i;
		if (q[front] < i - n + 1)
			front++;
		if (i >= n)
			d[++len1] = c[q[front]];
	}
}

void work2(int c[], int d[], int l) {
	front = 1, rear = 0;
	len2 = 0;
	for (int i = 1; i <= l; i++) {
		while (front <= rear && c[q[rear]] <= c[i])
			rear--;
		q[++rear] = i;
		if (q[front] < i - n + 1)
			front++;
		if (i >= n)
			d[++len2] = c[q[front]];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> a >> b >> n;
	for (int i = 1; i <= a; i++)
		for (int j = 1; j <= b; j++)
			cin >> c[i][j];
	for (int i = 1; i <= a; i++) {
		work1(c[i], Min[i], b);
		work2(c[i], Max[i], b);
	}
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= a; j++)
			tmp1[i] = Min[j][i], tmp2[i] = Max[j][i];
		int tmp = len1;
		work1(tmp1, p, tmp);
		work2(tmp2, r, tmp);
		int minn = 0x3f3f3f3f, maxx = -0x3f3f3f3f;
		for (int j = 1; j <= len1; j++)
		    ans = min(ans, r[j] - p[j]);
	}
	cout << ans << '\n';
	return 0;
}