o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p... TLE pe 3 teste ...
eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col...
apoi am sortat vectorul cu quicksort dupa val...
si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)...
si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)...
sugestii de optimizare?
Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare.
am incercat ce mi-ai sugerat. intr-adevar este mult mai rapid (inainte timpul maxim de executie pentru testele care intrau era 640ms acum este sub 180 ms)...dar tot da TLE pe 3 teste (aceleasi teste 4,7,9)...or fi cazuri particulare/speciale pe testele astea? (si poate nu le-am depistat eu)...
ideea sugerata de
andretti am implementat-o prin procedurile spre_dreapta si in_jos (lungimile respective salvandu-le in matricele dr si jos ).
{$Q-}
program rama_runda4;
type punct=record
val:longint;
lin,col:integer;
end;
mat=array[1..701,1..701]of integer;
vect=array[1..500001]of punct;
vector=array[1..701]of integer;
var a,jos,dr:mat;
ok:boolean; dreapta:vector;
n,m:longint;
v:vect;
nr,k:longint;
f,g:text;
procedure initializare;
var i,j:integer; c:char;
begin
readln(f,m,n);
for i:=1 to m do
begin
for j:=1 to n do begin
read(f,c);
if c='0' then a[i,j]:=0;
if c='1' then a[i,j]:=1;
end;
readln(f);
end;
end;
procedure quicksort(var a:vect;inf,sup:longint);
var i,j:longint; aux,pivot:punct;
begin
if (inf<sup)then begin
pivot:=a[inf];
i:=inf+1; j:=sup;
while (i<=j) do begin
while (i<=sup)and(a[i].val<=pivot.val) do inc(i);
while (j>=inf)and(a[j].val>pivot.val) do dec(j);
if (i<j)and(i>=inf)and(j<=sup)then begin
aux:=a[i];
a[i]:=a[j];
a[j]:=aux;
inc(i); dec(j);
end;
end;
dec(i);
a[inf]:=a[i]; a[i]:=pivot;
quicksort(a,inf,i-1);
quicksort(a,i+1,sup);
end;
end;
procedure drept(x,y:integer;var ok:boolean);
var p,i,j:integer; ok1:boolean;
begin
i:=1;
while (i<=m-x+1)and(dreapta[i]<y)do inc(i);
//verific daca fixand coltul stanga sus pe linia i am sanse sa gasesc lungimea y
while (i<=m-x+1)and ok do
begin
j:=1;
while ((dr[i,j]<y)or(jos[i,j]<x))and(j<=n-y+1)do inc(j);
//daca pe coloana j gasesc inaltimea x
while (j<=n-y+1)and ok do
begin
ok1:=true;
p:=i;
while (p<=i+x-1)and ok1 do
begin
if (a[p,j]=0)or(a[p,j+y-1]=0)then ok1:=false;
inc(p);
end;
p:=j;
while (p<=j+y-1)and ok1 do
begin
if (a[i,p]=0)or(a[i+x-1,p]=0)then ok1:=false;
inc(p);
end;
if ok1 then begin
nr:=x*y; //am gasit solutia
ok:=false;//ma opresc
end;
inc(j);
end;
inc(i);
end;
end;
procedure spre_dreapta(var dr:mat);
var i,j,primu,dif,k:integer;
begin
for i:=1 to m do
begin
j:=1;
repeat
while (a[i,j]<>1)and(j<=n)do inc(j);
primu:=j;
while (a[i,j]=1)and(j<=n) do inc(j);
dif:=j-primu; if dif>dreapta[i] then dreapta[i]:=dif;
for k:=primu to j-1 do
begin
dr[i,k]:=dif;
dec(dif);
end;
until j>n;
end;
end;
procedure in_jos(var jos:mat);
var i,j,primu,dif,k:integer;
begin
for j:=1 to n do
begin
i:=1;
repeat
while (a[i,j]<>1)and(i<=m)do inc(i);
primu:=i;
while (a[i,j]=1)and(i<=m) do inc(i);
dif:=i-primu;
for k:=primu to i-1 do
begin
jos[k,j]:=dif;
dec(dif);
end;
until i>m;
end;
end;
procedure cauta_dreptunghi;
var i,j,k:longint;
begin
//calculez toate ariile posibile i*j si le memorez in v
k:=0;
for i:=1 to m do
for j:=1 to n do
begin
inc(k);
v[k].val:=i*j;v[k].lin:=i;v[k].col:=j;
end;
quicksort(v,1,k);//ordonez vectorul crecator dupa arii
//pornesc cu cea mai mare arie. daca e buna ma opresc daca nu o iau pe urmatoarea(in ordine descrescatoare)
ok:=true; nr:=0;
while ok and(k>=1)do
begin
drept(v[k].lin,v[k].col,ok);
dec(k);
end;
writeln(g,nr);
end;
begin
assign(f,'rama.in');reset(f);
assign(g,'rama.out');rewrite(g);
initializare;
spre_dreapta(dr);
in_jos(jos);
cauta_dreptunghi;
close(f);close(g);
end.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena