fork(1) download
  1. { Zenit CK 2011/2012, uloha e)
  2.   Riesenie by Zemco
  3.  
  4.   Dynamicke programovanie, DP[i,j] znamena, aby najvacsi
  5.   otoceny stvorec ma dolny bod v mieste [i,j]?
  6.   Pocitame postupne pre zvacsujuce sa i a zvacsujuce sa j.
  7.   Cas O(R*C), pamat (R*C) dala by sa zlepsit.}
  8. uses math;
  9. var i,j,R,C: integer;
  10. M: array[1..1005,1..1005] of char;
  11. DP: array[1..1005,1..1005] of integer;
  12. best: integer;
  13. {cely vstup mame zapamatany v poli o dva riadky a stlpce posunute
  14.  pre zjednodusenie kodu. }
  15. begin
  16. best := 0;
  17. readln(R,C);
  18. for i:=1 to R+2 do for j:=1 to C+2 do DP[i,j] := 0;
  19. for i:=1 to R+2 do for j:=1 to C+2 do M[i,j] := '.';
  20. for i:=1 to R do
  21. begin
  22. for j:=1 to C do read(M[i+2,j+2]);
  23. readln;
  24. end;
  25. for i:=1 to R+2 do for j:=1 to C+2 do
  26. begin
  27. if (M[i,j] = '.') then DP[i,j] := 0
  28. else DP[i,j] := min( min( DP[i-1,j-1], DP[i-1,j+1]), min( DP[i-2,j], DP[i-1,j]) ) + 1;
  29. best := max(best, DP[i,j]);
  30. end;
  31. if (best = 0) then writeln(0)
  32. else writeln( (2*best-1)*(2*best-1) - 2*(best*(best-1) ) );
  33. end.
Success #stdin #stdout 0.02s 3360KB
stdin
Standard input is empty
stdout
0