http://acm.pku.edu.cn/JudgeOnline/problem?id=1156
Код:
program PKU1156; {$I-,S-,Q-,R-} const inf = ''; ouf = ''; maxn = 710; none = 1000000; type integer = longint; var h: array[0 .. maxn, 0 .. maxn] of integer; q, f: array[1 .. maxn, 1 .. 2] of integer; a, b: array[1 .. maxn] of integer; l, r: array[1 .. 2] of integer; buf: array[0..1 shl 19] of integer; n, m, limit: integer; function min(i, j: integer): integer; begin if i < j then min := i else min := j; end; procedure prepare; var i, j: integer; begin fillchar(h, sizeof(h), 0); assign(input, inf); settextbuf(input, buf); reset(input); read(m, n, limit); for i := 1 to n do for j := 1 to m do read(h[i, j]); close(input); end; var time: longint; procedure main; var i, j, k, tmp: integer; ans, nowans: integer; begin ans := 1; for i := 1 to m do begin for k := 1 to n do begin a[k] := none; b[k] := -none; end; for j := i to min(i + 99, m) do begin for k := 1 to n do begin if h[k, j] < a[k] then a[k] := h[k, j]; if h[k, j] > b[k] then b[k] := h[k, j]; end; l[1] := 1; r[1] := 0; l[2] := 1; r[2] := 0; for k := 1 to n do if b[k] - a[k] <= limit then begin while (l[1] <= r[1]) and (b[k] - a[q[l[1], 1]] > limit) do l[1] := l[1] + 1; while (l[2] <= r[2]) and (b[q[l[2], 2]] - a[k] > limit) do l[2] := l[2] + 1; tmp := k; while (l[1] <= r[1]) and (a[q[r[1], 1]] >= a[k]) do begin tmp := f[r[1], 1]; r[1] := r[1] - 1; end; r[1] := r[1] + 1; q[r[1], 1] := k; f[r[1], 1] := tmp; tmp := k; while (l[2] <= r[2]) and (b[q[r[2], 2]] <= b[k]) do begin tmp := f[r[2], 2]; r[2] := r[2] - 1; end; r[2] := r[2] + 1; q[r[2], 2] := k; f[r[2], 2] := tmp; if f[l[1], 1] > f[l[2], 2] then tmp := f[l[1], 1] else tmp := f[l[2], 2]; if (l[1] <= r[1]) and (l[2] <= r[2]) then begin nowans := (j - i + 1) * (k - tmp + 1); if nowans > ans then ans := nowans; end; if (j - i + 1) * (n - tmp + 1) <= ans then break; end else begin l[1] := 1; l[2] := 1; r[1] := 0; r[2] := 0; if (j - i + 1) * (n - k) <= ans then break; end; end; end; writeln(ans); end; begin prepare; main; end.