var
  a: Array[0..3001, 0..3001] of Boolean;
  n, m, i, j: Integer;
  q: Boolean;

procedure Vvod;
var
  ch: Byte;
begin
  readln(n, m);
  for j := 1 to n do
    for i := 1 to m do
    begin
      if i = m then
        readln(ch)
      else
        read(ch);
      if ch = 1 then
        a[i, j] := true;
    end;
end;

procedure Obnul(x, y: Integer);
begin
  if a[x, y] = false then
    Exit
  else
  begin
    a[x, y] := false;
    Obnul(x + 1, y);
    Obnul(x - 1, y);
    Obnul(x, y + 1);
    Obnul(x, y - 1);
  end;
end;

procedure Check;
var
  ii, jj, dlV, dlH: Integer;
begin
  for j := 1 to n do
    for i := 1 to m do
      if a[i, j] = true then
      begin
        jj := j;
        while a[i, jj] = true do
          inc(jj);
        dlV := jj - j;
        ii := i;
        while a[ii, j] = true do
          inc(ii);
        dlH := ii - i;


        for jj := j to j + dlV - 1 do
          for ii := i to i + dlH - 1 do
            if a[ii, jj] = false then
            begin
              writeln('No');
              q := false;
              Exit;
            end;

        for jj := j to j + dlV - 1 do
          if (a[i - 1, jj] = true) or (a[i + dlH, jj] = true) then
          begin
            writeln('No');
            q := false;
            Exit;
          end;


        for ii := i to i + dlH - 1 do
          if (a[ii, j - 1] = true) or (a[ii, j + dlV] = true) then
          begin
            writeln('No');
            q := false;
            Exit;
          end;

        Obnul(i, j);
      end;
end;

begin
  q := true;
  Vvod;
  Check;
  if q = true then
    writeln('Yes');
  readln;
end.

If I use Integer I have MLE 6 1.500 Kb and if i use ShortInt
I have WA 10 with memory 190 Kb!
Isn't it strange?

Freepascal organizes the memory allocation process in such a way that when you define an array of 3000x3000 and use only first 100 lines of it, then the memory usage will be 3000*100*sizeof(type), not 3000*3000.

When using shortint, you can never exceed 128, so your program is probably incorrect, but not running out of memory; nevertheless, this is a yes-no output problem, so the probability is high that you pass some tests with a wrong program.

Also note that Integer = Longint; if you want a 2-byte int, use Word or Smallint.

Edited by author 10.02.2006 15:10

3000*3000=9000000 9000 kb
your must use O(2*M) MEMORY