Cod sursa(job #929929)

Utilizator george_stelianChichirim George george_stelian Data 27 martie 2013 12:48:20
Problema Heavy metal Scor 40
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.94 kb
type formatie=record
     a,b:longint;
     end;

var f,g:text;v:array[1..100001]of formatie;v1:array[1..100001]of longint;
n,i,j,max,x:longint;

procedure sort(st,dr:longint);
var i,j,x:longint;aux:formatie;
begin
i:=st;j:=dr;x:=v[(st+dr)div 2].b;
repeat
 while v[i].b<x do inc(i);
 while v[j].b>x do dec(j);
 if i<=j then begin
 aux:=v[i];v[i]:=v[j];v[j]:=aux;
 inc(i);
 dec(j);
              end;
until i>j;
if st<j then sort(st,j);
if dr>i then sort(i,dr);
end;

begin
assign(f,'heavymetal.in');reset(f);assign(g,'heavymetal.out');rewrite(g);
read(f,n);
for i:=1 to n do read(f,v[i].a,v[i].b);
sort(1,n);
v1[1]:=v[1].b-v[1].a;
for i:=2 to n do begin
max:=0;
x:=0;
j:=i-1;
while j>x do begin
if (v[j].b<=v[i].a)and(v1[j]>max)then begin max:=v1[j];x:=v[j].a;end;
dec(j);
end;
if v1[i-1]>max+v[i].b-v[i].a then v1[i]:=v1[i-1]
else v1[i]:=max+v[i].b-v[i].a;
                 end;
write(g,v1[n]);
close(f);close(g);
end.