Cod sursa(job #137865)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 17 februarie 2008 15:41:26
Problema Heavy metal Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.13 kb
Program p2;
Var f,ff:text;
    n,i,j,m,nn,c,dm:longint;
    a,b,d:array[1..20000000] of longint;
procedure qsort(st,dr:longint);
var m,i,j,k,l:longint;
    aa,am,bm:longint;
begin
 m:=(st+dr) div 2;
 am:=b[m];
 bm:=d[m];
 i:=st;
 j:=dr;
 repeat
    while (b[i]<am)or((b[i]=am)and(d[i]<bm)) do inc(i);
    while (b[j]>am)or((b[i]=am)and(d[i]>bm)) do dec(j);
    if i<=j then
      begin
       aa:=a[i];
       a[i]:=a[j];
       a[j]:=aa;
       aa:=b[i];
       b[i]:=b[j];
       b[j]:=aa;
       aa:=d[i];
       d[i]:=d[j];
       d[j]:=aa;
       i:=i+1;j:=j-1;
      end;
 until(i>j);
 if i<=dr then qsort(i,dr);
 if j>=st then qsort(st,j);

end;

Begin
  assign(f,'heavymetal.in');
  reset(f);
  assign(ff,'heavymetal.out');
  rewrite(ff);
  readln(f,n);
  for i:=1 to n do
     begin
      readln(f,a[i],b[i]);
      d[i]:=b[i]-a[i];
     end;
  qsort(1,n);
  m:=0;
  for nn:=n downto 1 do
  if m<b[nn] then
  begin
  c:=nn;
  dm:=d[c];
  for i:=nn-1 downto 1 do
     if b[i]<=a[c] then begin c:=i; dm:=dm+d[c]; end;
  if m<dm then m:=dm;
  end;
  Writeln(ff,m);
  close(f);
  close(ff);
End.