Salut. Sunt incepator in C++. Nu stiu de ce in codul urmator timp este trunchiat la partea intreaga.

long double timp;
timp=d*3600/vi;  //d,vi sunt int-uri

[andretti]

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 ).

Cod:

 
{$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.

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.

mersi. incerc sa implementez ce mi-ai zis. revin cu rezultatul

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?

si rezultatele cand se dau?

Bafta tuturor !

dap. am inteles. mersi

    Salut. Poate cineva sa-mi spuna cum pot masura timpul de executiei al programului meu in Free Pascal ?
    De ex. daca problema mea are 2 cerinte , si mi-a facut-o pe prima , vreau sa stiu daca mai am timp sa o fac si pe a doua pe testul respectiv, sau trebuie sa dau primul rezultat si sa se opreasca programul.

Multumesc !

    Salut. As vrea sa stiu daca insotitorul pentru oni trebuie sa fie obligatoriu profesor ? profesor de  informatica ?
    Fratele meu (clasa a 7-a) nu face informatica la scoala. S-a pregatit cu profesorul meu de la liceu. Dansul merge cu mine la Timisoara si ceilalti profesori de informatica de la mine din liceu nu vor sa plece cu fratimio (sau cu mine si sa mearga dansul cu fratimio)...situatie similara cam cu toti profesorii de informatica din judet (sunt si cativa care ar vrea sa mearga din alte orase dar din motive care nu tin nici de noi , nici de dansii , nu pot merge...) .    
    Si ma gandeam daca se poate sa rog un profesor de-al meu / de-al lui de matematica (sau de altceva) sa mearga cu el ... Nu as vrea sa mearga cu un profesor pe care nu-l cunosc eu sau fratimio , pentru ca e mai mic (13 ani)  ...
    Ce se poate face in situatia asta?
    As vrea si un raspuns din partea unui profesor daca se poate... (Am solicitat si inspectoratului sa intrebe organizatorii , da mi s-a spus ca pana dupa Olimpiada de TIC nu o sa intrebe nimeni ... si cred ca nici dupa nu o sa se grabeasca cineva...iar fratimio este putin cam trist ca nu are cine sa vina cu el ... parintele ar fi o optiune ? ).
    Multumesc!

aha.ok. mai astept si alte raspunsuri

Salut ! Am un frate mai mic (clasa a 7 a). Participa la ONI Oradea.  Stiti cumva daca are site olimpiada pentru gimnaziu ?  sau unde gasesc mai multe detalii despre ea ... multumesc  !

Ma poate ajuta cineva la problema urmatoare?

Olimpiada Judeţeană de Informatică
9 martie 2002, ora 900
CLASELE XI-XII
Problema 1 (Urgenţa)

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai efici¬ent la frecventele calamităţi naturale din zonă. În acest scop au identificat N puncte de interes strategic şi le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.
În cazul unei calamităţi unele căi de acces pot fi temporar întrerupte şi astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în aşa fel încât între oricare două puncte din acelaşi grup să existe măcar un drum şi între oricare două puncte din grupuri diferite să nu existe drum.
Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de K grupuri.

Date de intrare
Fişierul de intrare URGENTA.IN are următorul format:
N M K
i1 j1 p1    – între punctele i1 şi j1 există o cale de acces de prioritate p1
i2 j2 p2    – între punctele i2 şi j2 există o cale de acces de prioritate p2
...
iM jM pM    – între punctele iM şi jM există o cale de acces de prioritate pM

Date de ieşire
Fişierul de ieşire URGENTA.OUT va avea următorul format:
gravmax   – gravitatea maximă
C   – numărul de căi de acces întrerupte de calamitate
k1 h1    – între punctele k1 şi h1 a fost întreruptă calea de acces
k2 h2     – între punctele k2 şi h2 a fost întreruptă calea de acces
...
kC hC     – între punctele kC şi hC a fost întreruptă calea de acces

Restricţii şi precizări
0<N<256
N-2<M<32385
0<K<N+1
Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât 256.
Un grup de puncte poate conţine între 1 şi N puncte inclusiv.
Dacă există mai multe soluţii, programul va determina una singură.

Exemplu
URGENTA.IN   
7 11 4
1 2 1
1 3 2
1 7 3
2 4 3
3 4 2
3 5 1
3 6 1
3 7 5
4 5 5
5 6 4
6 7 3   


URGENTA.OUT
27
8
1 3
1 7
2 4
3 4
3 7
4 5
5 6
6 7

Timp maxim de executare:  1 secundă / test

repp4radu a pus mai sus 2 intrebari si i-ai raspuns cu NU

Punctele sunt sortate?
LE: Pot exista 2 pct cu aceleasi coordonate?

nu pentru amandoua?

si pentru complexitate ?
eu programez in pascal:d

Salut. Poate sa-mi explice careva care e diferenta intre memorie si memoria pentru stiva? si cum le calculez pe amandoua....
de la o anumita complexitate O(f(n)) , cum as sti pentru un n dat la ce timp  ma duce (de ce ordin- cateva sute de ms , secunde etc)?
Multumesc !