(* O(n^4) algorithm. Assume array entries are nonnegative and uses sentinels in row and column 0. Also uses arrays H[i,j] which contains the number of horizontally adjacent nonmonotonic pairs in the submatrix A[1..i, 1..j], and V[i,j] which contains the number vertically adjacent nonmonotonic pairs. (I don't see how to do it with just one array.) *) program monotone(input, output); const maxrow = 100; maxcol = 100; var A: array [0..maxrow, 0..maxcol] of integer; H: array [0..maxrow, 0..maxcol] of integer; V: array [0..maxrow, 0..maxcol] of integer; m : integer; n : integer; i, j : integer; i1, i2, j1, j2 : integer; maxsize, thissize : integer; i1s, i2s, j1s, j2s : integer; mems : integer; procedure Monot; begin maxsize := 0; mems := 0; for i := 0 to m do begin (* init sentinels *) A[i, 0] := -1; H[i, 0] := 0; V[i, 0] := 0; end; mems := mems + 2*(m+1); for j := 0 to n do begin A[0, j] := -1; H[0, j] := 0; V[0, j] := 0; end; mems := mems + 3*(n+1); for i := 1 to m do begin for j := 1 to n do begin H[i,j] := H[i-1,j] + H[i,j-1] - H[i-1,j-1]; V[i,j] := V[i-1,j] + V[i,j-1] - V[i-1,j-1]; if (A[i,j-1] > A[i,j]) then begin H[i,j] := H[i,j] + 1; end; if (A[i-1,j] > A[i,j]) then begin V[i,j] := V[i,j] + 1; end; end; end; mems := mems + 12 * m * n; for i1 := 1 to m do begin for j1 := 1 to n do begin for i2 := i1 to m do begin for j2 := j1 to n do begin if ( (H[i2,j2]-H[i1-1,j2]-H[i2,j1]+H[i1-1,j1] = 0) and (V[i2,j2]-V[i2,j1-1]-V[i1,j2]+V[i1,j1-1] = 0)) then begin thissize := (i2-i1+1) * (j2-j1+1); if (thissize > maxsize) then begin maxsize := thissize; i1s := i1; i2s := i2; j1s := j1; j2s := j2; end; mems := mems + 8; end; end; end; end; end; { writeln('Millions of memory access = ', mems/1000000:8:3); } end; begin (* the following eof loop is not required by contest specs *) while (not eof(input)) do begin readln(m, n); for i := 1 to m do begin for j := 1 to n do read(A[i,j]); readln; end; Monot; for i := i1s to i2s do begin for j := j1s to j2s do begin write(A[i,j]:2); if ( j < j2s) then write(' '); end; writeln; end; end; end.