Cod sursa(job #710)

Utilizator VmanDuta Vlad Vman Data 11 decembrie 2006 19:12:07
Problema Secventa 3 Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.76 kb
program secv3;
var c,t,h,aux:array[0..30000]of longint;
    n,l,u,i,j,fiu,tata,p:integer;
    f:text;
    max:real;
procedure citire;
begin
assign(f,'secv3.in');reset(f);
readln(f,n,l,u);
for i:=1 to n do begin
  read(f,c[i]);
  c[i]:=c[i]+c[i-1];
end;
for i:=1 to n do begin
  read(f,t[i]);
  t[i]:=t[i]+t[i-1];
end;
close(f);
end;

function maimic(a,b:integer):boolean;
begin
if (c[p]-c[a-1])/(t[p]-t[a-1])<(c[p]-c[b-1])/(t[p]-t[b-1]) then maimic:=true
  else maimic:=false;
end;

procedure up;
var a:integer;
begin
while (tata<>0)and(maimic(h[tata],h[fiu])) do begin
  a:=h[fiu];
  h[fiu]:=h[tata];
  h[tata]:=a;
  aux[h[fiu]]:=fiu;
  aux[h[tata]]:=tata;
  fiu:=tata;
  tata:=fiu div 2;
end;
end;

procedure down;
var a:integer;
    ok:boolean;
begin
tata:=fiu;
fiu:=fiu*2;
ok:=true;
while (tata>u-l+1)and ok do begin
ok:=false;
while (maimic(h[tata],h[fiu])) do begin
  ok:=true;
  a:=h[fiu];
  h[fiu]:=h[tata];
  h[tata]:=a;
  aux[h[fiu+1]]:=fiu+1;
  aux[h[tata]]:=tata;
  tata:=fiu;
  fiu:=fiu*2;
end;
while (maimic(h[tata],h[fiu+1])) do begin
  ok:=true;
  a:=h[fiu+1];
  h[fiu+1]:=h[tata];
  aux[h[fiu+1]]:=fiu+1;
  aux[h[tata]]:=tata;
  tata:=fiu+1;
  fiu:=fiu*2;
end;
end;
end;

procedure insertheap(val,poz:integer);
begin
if p<=u then begin
   if p>=l then
   fiu:=poz;
   tata:=fiu div 2;
   h[fiu]:=val;
   aux[fiu]:=poz;
   up;
   end
  else begin
   fiu:=aux[p-u+l-2];
   h[fiu]:=val;
   tata:=fiu div 2;
   aux[h[fiu]]:=fiu;
   aux[h[tata]]:=tata;
   up;
   down;
  end;
if (c[p]-c[h[1]-1])/(t[p]-t[h[1]-1])>max then max:=(c[p]-c[h[1]-1])/(t[p]-t[h[1]-1]);
end;

begin
citire;
for p:=l to n do
  insertheap(p-l+1,p-l+1);
assign(f,'secv3.out');rewrite(f);
writeln(f,max:0:2);
close(f);
end.