Cod sursa(job #152291)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 9 martie 2008 12:22:37
Problema Heavy metal Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.94 kb
type date=record a,b:longint; end;
     list=array[0..100000] of date;

procedure quicksort(var a: list; Lo,Hi: longint);

procedure sort(l,r: integer);
var
  i,j: longint;
  x,y: date;
begin
  i:=l; j:=r; x:=a[(l+r) DIV 2];
  repeat
    while a[i].b<x.b do i:=i+1;
    while x.b<a[j].b do j:=j-1;
    if i<=j then
    begin
      y:=a[i]; a[i]:=a[j]; a[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;

var n,i,cnd,max:longint;
    a:list;
    X:array[0..100000] of longint;


procedure citire;
        var f:text;
            i:longint;
        begin
        assign(f,'heavymetal.in');
         reset(f);
         readln(f,n);
         for i:=1 to n do
             readln(f,a[i].a,a[i].b);
         close(f);
        end;

procedure scrie(k:longint);
        var f:text;
        begin
        assign(f,'heavymetal.out');
         rewrite(f);
         writeln(f,k);
         close(f);
        end;

function cauta(x,lo,hi:longint):longint;
        var m:longint;
        begin
        while lo<=hi do
              begin
              m:=(hi+lo) div 2;
              if (a[m].b <= x) then
                lo:=m+1
              else
                if (a[m].b>x) then
                   hi:=m-1;
              end;
        if (a[m].b=x) then
            cauta:=m
        else
           begin
           m:=lo;
           if (a[m].b>x) then
              m:=hi;
           cauta:=m;
           end;
        end;

begin
citire;
quicksort(a,1,n);

x[0]:=0;
x[1]:=a[1].b-a[1].a;

for i:=2 to n do
    begin
    x[i]:=x[i-1];
    cnd:=cauta(a[i].a,1,i);
    if x[i]<x[cnd]+(a[i].b-a[i].a) then
       x[i]:=x[cnd]+(a[i].b-a[i].a);
    end;
max:=x[n];
i:=i-1;
while (a[n].b=a[i].b) do
        begin
        if max<x[i] then
           max:=x[i];
        dec(i);
        end;
scrie(max);
end.