Pagini recente » Cod sursa (job #948439) | Cod sursa (job #331241) | Cod sursa (job #1920412) | Cod sursa (job #2949632) | Cod sursa (job #167230)
Cod sursa(job #167230)
type trio=record
a,b,s:longint;
end;
var fi,fo:text;
n,i:longint;
v:array[0..100000]of trio;
procedure down(i,n:longint);
var fiu,tata:longint;
l:trio;
begin
l:=v[i]; tata:=i; fiu:=i shl 1;
while fiu<=n do
begin
if fiu<n then
if v[fiu].b<v[fiu+1].b then inc(fiu);
if l.b<v[fiu].b then
begin
v[tata]:=v[fiu];
tata:=fiu;
fiu:=fiu shl 1;
end
else fiu:=n+1;
end;
v[tata]:=l;
end;
procedure heapsort;
var i,aux:longint;
m:trio;
begin
aux:=n shr 1;
for i:=aux downto 1 do
down(i,n);
for i:=n downto 2 do
begin
m:=v[i];
v[i]:=v[1];
v[1]:=m;
down(1,i-1);
end;
end;
function search(st,dr,vl:longint):longint;
var mij,poz,max:longint;
begin
max:=0; poz:=0;
while st<=dr do
begin
mij:=(st+dr) shr 1;
if v[mij].b<=vl then
begin
if v[mij].s>max then
begin
max:=v[mij].s;
poz:=mij;
end;
st:=mij+1;
end
else dr:=mij-1;
end;
search:=poz;
end;
procedure solve;
var i,aux:longint;
begin
for i:=1 to n do
begin
aux:=search(1,i-1,v[i].a);
if v[aux].s+v[i].b-v[i].a>v[i-1].s then
v[i].s:=v[aux].s+v[i].b-v[i].a
else
v[i].s:=v[i-1].s;
end;
writeln(fo,v[n].s);
end;
begin
assign(fi,'heavymetal.in'); reset(fi);
assign(fo,'heavymetal.out'); rewrite(fo);
read(fi,n);
for i:=1 to n do
read(fi,v[i].a,v[i].b);
heapsort;
solve;
close(fi);
close(fo);
end.