Cod sursa(job #137773)

Utilizator ProtomanAndrei Purice Protoman Data 17 februarie 2008 14:41:02
Problema Heavy metal Scor 40
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.65 kb
type interval=record
              s,f,sm,st:longint;
     end;

var f1,f2:text;
    i,j,n,mx:longint;
    a:array[0..100000] of interval;

procedure pozitie(var m:longint; p,u:longint);
var i,j,di,dj,aux2:longint;
    aux:interval;
begin
        i:=p;
        j:=u;
        di:=0;
        dj:=-1;
        while i<j do
        begin
                if (a[i].s>a[j].s)or((a[i].s=a[j].s)and(a[i].f>a[j].f)) then
                begin
                        aux:=a[i];
                        a[i]:=a[j];
                        a[j]:=aux;
                        aux2:=di;
                        di:=-dj;
                        dj:=-aux2;
                end;
                i:=i+di;
                j:=j+dj;
        end;
        m:=i;
end;

procedure quick(p,u:longint);
var m:longint;
begin
        if p<u then
        begin
                pozitie(m,p,u);
                quick(p,m-1);
                quick(m+1,u);
        end;
end;

begin
        assign(f1,'heavymetal.in');
        reset(f1);
        assign(f2,'heavymetal.out');
        rewrite(f2);
        read(f1,n);
        for i:=1 to n do
        begin
                read(f1,a[i].s,a[i].f);
                a[i].sm:=a[i].f-a[i].s;
                a[i].st:=a[i].sm;
        end;
        quick(1,n);
        for i:=1 to n do
                for j:=1 to i-1 do
                        if (a[i].sm+a[j].st>a[i].st)and(a[i].s>=a[j].f) then
                                a[i].st:=a[i].sm+a[j].st;
        for i:=1 to n do
                if a[i].st>mx then
                        mx:=a[i].st;
        writeln(f2,mx);
        close(f1);
        close(f2);
end.