Cod sursa(job #282537)

Utilizator cristinabCristina Brinza cristinab Data 17 martie 2009 21:10:21
Problema Heavy metal Scor 40
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.55 kb
type concert=record
             int1,int2:longint;
             end;

var a:array[1..100000] of concert;
    suma:array[1..100000] of integer;
    n,i,suma_max:longint;
    g:text;

procedure qsort(l,r:longint);
var i,j,x1,x2:longint;
    aux:concert;
begin
i:=l;
j:=r;
x2:=a[(l+r) div 2].int2;

repeat
while a[i].int2<x2 do inc(i);
while a[j].int2>x2 do dec(j);

if i<=j then
   begin
   aux:=a[i];
   a[i]:=a[j];
   a[j]:=aux;
   inc(i);
   dec(j);
   end
else if (a[i].int2=a[j].int2) and (a[i].int1>a[j].int1) then
        begin
        aux:=a[i];
        a[i]:=a[j];
        a[j]:=aux;
        end;

until i>=j;

if j>l then qsort(l,j);
if i<r then qsort(i,r);

end;


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].int1,a[i].int2);
close(f);
end;


procedure rezolvare;
var i,j,numar:longint;
begin
qsort(1,n);

for i:=1 to n do
    begin
    suma[i]:=a[i].int2-a[i].int1;
    for j:=1 to i-1 do
        if a[j].int2<=a[i].int1 then
           begin
           numar:=suma[j]+a[i].int2-a[i].int1;
           if numar>suma[i] then suma[i]:=numar;
           end
        else begin
             numar:=suma[j]-(a[i].int2-a[i].int1);
             if suma[i]<numar then suma[i]:=numar;
             end;
    if suma[i]>suma_max then suma_max:=suma[i];
    end;

end;

procedure afisare;
begin
assign(g,'heavymetal.out'); rewrite(g);
writeln(g,suma_max);
close(g);
end;

begin
citire;
rezolvare;
afisare;
end.