Cod sursa(job #972392)

Utilizator t.g.g.tt.g.g.t t.g.g.t Data 11 iulie 2013 16:23:43
Problema Secventa 3 Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.06 kb
var a:array[0..30001]of integer;
    b:array[0..30001]of integer;
    c:array[1..2,0..30001]of longint;
    n,l,u,t,ult,i:integer;
    max:real;
    buf:array[1..1 shl 14]of char;

procedure inserare(pos:integer);
  var t:integer;
  begin
    if pos<>1 then
      begin
        if ((c[1,i]-c[1,a[pos]-1])/(c[2,i]-c[2,a[pos]-1])>(c[1,i]-c[1,a[pos div 2]-1])/(c[2,i]-c[2,a[pos div 2]-1])) then
          begin
            b[a[pos]]:=pos div 2; b[a[pos div 2]]:=pos;
            t:=a[pos]; a[pos]:=a[pos div 2]; a[pos div 2]:=t; inserare(pos div 2);
          end;
      end;
  end;

procedure coboara (pos:longint);
  var min,t:longint;
  begin
    if pos<=ult then
      begin
        if ((c[1,i]-c[1,a[pos]-1])/(c[2,i]-c[2,a[pos]-1])>(c[1,i]-c[1,a[pos div 2]-1])/(c[2,i]-c[2,a[pos div 2]-1])) then min:=pos else min:=pos div 2;
        if pos<ult then
          if ((c[1,i]-c[1,a[pos+1]-1])/(c[2,i]-c[2,a[pos+1]-1])>(c[1,i]-c[1,a[min]-1])/(c[2,i]-c[2,a[min]-1])) then min:=pos+1;
        if min<>pos div 2 then
          begin
            b[a[min]]:=pos div 2; b[a[pos div 2]]:=min;
            t:=a[min]; a[min]:=a[pos div 2]; a[pos div 2]:=t;
            coboara(min*2);
          end;
      end;
  end;

begin
  assign(input,'secv3.in'); reset(input); settextbuf(input,buf);
  readln(n,l,u);
  for i:=1 to n do begin read(t); c[1,i]:=c[1,i-1]+t; end;
  for i:=1 to n do begin read(t); c[2,i]:=c[2,i-1]+t; end;
  ult:=0;
  for i:=l to u do
    begin
      inc(ult); b[i-l+1]:=ult; a[ult]:=i-l+1;
      inserare(ult);
      if (max<(c[1,i]-c[1,a[1]-1])/(c[2,i]-c[2,a[1]-1])) then max:=(c[1,i]-c[1,a[1]-1])/(c[2,i]-c[2,a[1]-1]);
    end;
  for i:=u+1 to n do
    begin
      inc(ult); b[i-l+1]:=ult; a[ult]:=i-l+1;
      inserare(ult);
      dec(ult);
      a[b[i-u]]:=a[ult+1]; b[a[ult+1]]:=b[i-u];
      coboara(b[i-u]*2);a[ult+1]:=0;
      if (max<(c[1,i]-c[1,a[1]-1])/(c[2,i]-c[2,a[1]-1])) then max:=(c[1,i]-c[1,a[1]-1])/(c[2,i]-c[2,a[1]-1]);
    end;
  assign(output,'secv3.out'); rewrite(output);
  writeln(max:0:2);
  close(output);
end.