Pagini recente » Cod sursa (job #2633371) | Cod sursa (job #1496896) | Cod sursa (job #736796) | Cod sursa (job #654522) | Cod sursa (job #137496)
Cod sursa(job #137496)
program stalpi;
type stalp = record
x,s,d,c:longint;
end;
var f:text;
n,i,j:longint;
v:array[1..100000] of stalp;
a,b:array[1..100000] of extended;
procedure qsort(bal,jobb:longint);
var i,j,va:longint;
cs:stalp;
begin
i:=bal;j:=jobb;
va:=v[(i+j) div 2].x;
while (i<=j) do
begin
while(v[i].x < va) do inc(i);
while(v[j].x > va) do dec(j);
if(i<=j) then
begin
cs:=v[i];
v[i]:=v[j];
v[j]:=cs;
inc(i);dec(j);
end;
end;
if(bal<j) then qsort(bal,j);
if(i<jobb) then qsort(i,jobb);
end;
function jobbra(x:longint):longint;
var i:longint;
begin
i:=x;
while(v[x].d+v[x].x >= v[i].x) and (i<=n) do inc(i);
jobbra:=i-x-1;
end;
function balra(x:longint):longint;
var i:longint;
begin
i:=x;
while(v[x].x-v[x].s <= v[i].x) and (i>0) do dec(i);
balra:=x-i-1;
end;
begin
assign(f,'stalpi.in');
reset(f);
readln(f,n);
for i:=1 to n do
readln(f,v[i].x,v[i].c,v[i].s,v[i].d);
close(f);
qsort(1,n);
for i:=1 to n do
begin
v[i].s:=balra(i);
v[i].d:=jobbra(i);
end;
for i:=1 to n do
begin
a[i]:=v[i].c;
if(i-v[i].s-1 > 0) then a[i]:=a[i]+b[i-v[i].s-1];
if(a[i] < b[i]) or (b[i] = 0) then b[i]:=a[i];
for j:=i-v[i].s to i-1 do
if (a[i] < b[j]) then b[j]:=a[i];
for j:=i+1 to i+v[i].d do
if (b[j] = 0) or (a[i] < b[j]) then b[j]:=a[i];
end;
assign(f,'stalpi.out');
rewrite(f);
writeln(f,b[n]:0:0);
close(f);
end.