Cod sursa(job #150263)

Utilizator dascalu2Dascalu Andi FLorin dascalu2 Data 6 martie 2008 19:57:10
Problema Heavy metal Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.18 kb
type list=array[0..100000]of longint;
var i,n,c,p,u,m,max:longint;
    vx,vy,a:list;
procedure QuickSort(var A: List; Lo, Hi: Integer);

procedure Sort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := a[(l+r) DIV 2];
  repeat
    while a[i] < x do i := i + 1;
    while x < a[j] do j := j - 1;
    if i <= j then
    begin
      y := a[i]; a[i] := a[j]; a[j] := y;
      y := vx[i]; vx[i] := vx[j]; vx[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin {QuickSort};
  Sort(Lo,Hi);
end;
begin
assign(input,'heavymetal.in');
reset(input);
read(n);
for i:=1 to n do
read(vx[i],vy[i]);
close(input);
quicksort(vy,1,n);
vx[0]:=1;
vy[0]:=1;
for i:=1 to n do
begin
     p:=0;
     u:=n;
     while(p<=u)do
     begin
          m:=(p+u) div 2;
          if(vy[m]>=vx[i])then
          u:=m-1
          else
          p:=m+1;
     end;
     if(vy[p]>vx[i])then
     p:=p-1;
     a[i]:=vy[i]-vx[i]+a[p];

end;
assign(output,'heavymetal.out');
rewrite(output);
max:=0;
for i:=1 to n do
    if a[i]>max then
    max:=a[i];
write(a[i]);
close(output);
end.