Cod sursa(job #283509)

Utilizator Cristian_BBerceanu Cristian Cristian_B Data 19 martie 2009 11:28:59
Problema Heavy metal Scor 10
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.56 kb
var sa,sb,a,b,c:array[1..100000] of longint;
    s,ret,k,max,i,j,n:longint;
    f,g:text;
    ok:boolean;
procedure load;
var i,j:longint;
begin
assign(f,'heavymetal.in');
reset(f);
readln(f,n);
for i:=1 to n do
readln(f,a[i],b[i]);
close(f);
assign(g,'heavymetal.out');
rewrite(g);
end;
function intersect(x,y,z,t:longint):boolean;
var ok:boolean;
begin
 ok:=true;
 if (x<=y) and (x<=z) and (y<=z) and (x<=t) and (y<=t) then ok:=false;
  if (z<=t) and (z<=x) and (z<=y) and (t<=x) and (t<=y)  then ok:=false;
 intersect:=ok;
end;
procedure init_c;
var i:longint;
begin
for i:=1 to n do
 c[i]:=b[i]-a[i];
end;

function exista:boolean;
var ok:boolean;
    i,j:longint;
begin
 ok:=false;
 for i:=1 to n do
 for j:=1 to k do
 if intersect(a[i],b[i],sa[j],sb[j])=false then ok:=true;
 exista:=ok;
end;
function minus:boolean;
var ok:boolean;
    i:longint;
begin
ok:=false;
for i:=1 to n do
if c[i]<>-1 then ok:=true;
minus:=ok;
end;

BEGIN
load;
init_c;
max:=c[1];
ret:=1;
k:=0;
for i:=2 to n do
 if max<c[i] then
 begin
  max:=c[i];
  ret:=i;
 end;
  c[ret]:=-1;
  k:=k+1;
  sa[k]:=a[ret];
  sb[k]:=b[ret];
  s:=b[ret]-a[ret];
i:=0;
while (exista) and (minus) do
begin
 max:=-2;
 for i:=1 to n do
  if max<c[i] then
   begin
    max:=c[i];
    ret:=i;
    c[i]:=-1;
   end;
  ok:=false;
  for i:=1 to k do
  if intersect(sa[i],sb[i],a[ret],b[ret])=true then ok:=true;
  if not ok then
  begin
   k:=k+1;
   sa[k]:=a[ret];
   sb[k]:=b[ret];
   s:=s+b[ret]-a[ret];
  end;
end;
writeln(g,s);
close(g);
END.