Pagini recente » Cod sursa (job #2854442) | Cod sursa (job #2150565) | Cod sursa (job #2887892) | Cod sursa (job #3257653) | Cod sursa (job #283554)
Cod sursa(job #283554)
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:=1;
s:=0;
sa[1]:=a[1];
sb[1]:=b[1];
s:=s+b[1]-a[1];
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:=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.