MTHCN spoj – Hình chữ nhật kì lạ

const fi='; fo='; nmax=1000; maxsang=997; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of longint; n,m:data; D,S,L,R:array[1..1000*1000] of longint; ns:data; dd:array[0..maxsang] of boolean; spt:data; snt:array[1..168] of data; Ans:data; function chinhphuong(x:data):boolean; begin exit(sqr(trunc(sqrt(x)))=x); end; function TKNP(x:data):boolean; var l,r,mid:longint; begin l:=1; r:=spt; while l<=r do begin mid:=(l+r) div 2; if snt[mid]=x then exit(true) else if snt[mid]>x then r:=mid-1 else l:=mid +1; end; exit(false); end; procedure sangNT; var i,j:data; begin fillchar(dd,sizeof(dd),true); dd[1]:=false; i:=2; while i<=trunc(sqrt(maxsang)) do begin while not dd[i] do inc(i); for j:=2 to maxsang div i do dd[i*j]:=false; inc(i); end; spt:=0; for i:=2 to maxsang do if dd[i] then begin inc(spt); SNT[spt]:=i*i*i; end; end; procedure xuli; var i,j,dientich:data; begin fillchar(d,sizeof(d),0); for i:=1 to n do begin for j:=1 to n do if a[i,j]<>1 then d[j]:=i; ns:=0; // ns la spt cua stack S; for j:=1 to n do begin while (ns>0) and (d[s[ns]]<=d[j]) do dec(ns); if ns=0 then L[j]:=0 else L[j]:=s[ns]; // l]j] la bien trai inc(ns); s[ns]:=j; end; ns:=0; for j:=n downto 1 do begin while (ns>0) and (d[s[ns]]<=d[j]) do dec(ns); if ns=0 then R[j]:=n+1 else R[j]:=s[ns]; // r[j] la bien phai; inc(ns); s[ns]:=j; end; for j:=1 to n do begin dientich:=(i-d[j])*(R[j]-L[j]-1); if ans<dientich then ans:=dientich; end; end; assign(f,fo); rewrite(f); writeln(f,ans); close(f); end; procedure docfile; var i,j,u,v,x:data; k:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=0 to n+1 do for j:=0 to n+1 do A[i,j]:=0; for i:=1 to m do begin readln(f,x,u,v,k); A[x,u]:=a[x,u]+k; A[x,v+1]:=a[x,v+1]-k; end; for i:=1 to n do for j:=1 to n do A[i,j]:=a[i,j-1]+a[i,j]; for i:=1 to n do for j:=1 to n do if chinhphuong(a[i,j]) or tknp(a[i,j]) then A[i,j]:=1 else A[i,j]:=0; close(f); end; begin sangnt; docfile; xuli; end.