Cod sursa(job #152278)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 9 martie 2008 12:14:42
Problema Heavy metal Scor 50
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.82 kb
type date=record a,b:longint; end;
     list=array[1..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:longint;
    a:list;
    X:array[1..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:longint):longint;
        var lo,hi,m:longint;
        begin
        lo:=1;
        hi:=n;
        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[1]:=a[1].b-a[1].a;

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