Pagini recente » Cod sursa (job #1774399) | Cod sursa (job #209502) | Cod sursa (job #1403884) | Cod sursa (job #602200) | Cod sursa (job #137354)
Cod sursa(job #137354)
type roaker=record
x,y:longint;
end;
var n,i,j,poz,p1,p2:longint;
aux:roaker;
v:array[0..100010] of roaker;
x,y:array[0..100100] of longint;
procedure qsort(ls,ld:longint);
var i,j:longint;
begin
i:=ls;j:=ld;
while true do begin
while (v[i].y<=v[j].y)and(i<>j) do inc(i);
if i=j then break;
aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
while (v[i].y<=v[j].y)and(i<>j) do dec(j);
if i=j then break;
aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
end;
if j-1>ls then qsort(ls,j-1);
if j+1<ld then qsort(j+1,ld);
end;
function cauta(l,r:longint):longint;
var m:longint;
begin
m:=(l+r) div 2;
if (v[m].y<=v[i].x)and((v[m+1].y>v[i].x)or(m+1=i)) then
begin
cauta:=m;
exit;
end;
if l>=r then
begin
cauta:=0;
exit;
end;
if v[m].y<=v[i].x then
cauta:=cauta(m+1,r);
if v[m].y>v[i].x then
cauta:=cauta(l,m-1);
end;
function max(a,b:longint):longint;
begin
if a>b then
max:=a
else
max:=b;
end;
begin
assign(input,'heavymetal.in');reset(input);
assign(output,'heavymetal.out');rewrite(output);
readln(n);
for i:=1 to n do
readln(v[i].x,v[i].y);
randomize;
for i:=1 to n div 2 do
begin
p1:=random(n)+1;
p2:=random(n)+1;
aux:=v[p1];v[p1]:=v[p2];v[p2]:=aux;
end;
qsort(1,n);
//x[i]=daca l-am luat pe i
x[1]:=v[1].y-v[1].x;
for i:=2 to n do
begin
if v[i].x<v[1].x then
poz:=0
else
poz:=cauta(1,i-1);
x[i]:=max(x[poz],y[poz])+v[i].y-v[i].x;
y[i]:=max(x[i-1],y[i-1]);
end;
writeln(max(x[n],y[n]));
close(input);close(output);
end.