Thứ Ba, 3 tháng 5, 2022

NHAHANG PASCAL

const
   fin='NHAHANG.inp';   fon='NHAHANG.out';
   vc=1000000000000;
   nmax = 50000+5;
type Tpt = record
        a,b:int64;
        end;
var
   c:array[-1..nmax] of Tpt;
   f,t,kq:array[-1..nmax] of int64;
   n,i,p:longint;
function ss(x,y:tpt):boolean;
begin
        if x.a<y.a then exit(true);
        exit(false);
end;

procedure qs(l,r:longint);
var i,j:longint;
x,t:tpt;
begin
   x:=c[(l+r) div 2];
   i:=l;j:=r;
   repeat
      while ss(c[i],x)=true do inc(i);
      while ss(x,c[j])=true do dec(j);
      if i<=j then
         begin
         t:=c[i];c[i]:=c[j];c[j]:=t;
         inc(i);dec(j);
         end;
   until i>j;
   if L<j then qs(l,j);
   if i<r then qs(i,r);
   end;


procedure xuli;
var
        i,j,jmax,z,d:longint;
begin
qs(1,n);
//for i:=1 to n do
 //       writeln(c[i].a,' ',c[i].b);

c[0].a:=0;c[0].b:=0;c[n+1].a:=vc; c[n+1].b:=1;
f[-1]:=-vc;
for i:=1 to n+1 do
   begin
   jmax:=-1;
   for j:=0 to i-1 do
      if (c[i].a-c[j].a>=p) then
         if (f[j]>f[jmax]) then jmax:=j;
   if jmax=-1 then f[i]:=0
   else f[i]:=f[jmax]+c[i].b;
   t[i]:=jmax;
   end;
{truy vet}
z:=t[n+1];
d:=0;
repeat
   inc(d);
   kq[d]:=z;
   z:=t[z];
until z=0;

writeln(f[n+1]-1);
//writeln(d);
//for i:=d downto 1 do writeln(kq[i],' ');

end;

begin
    assign(input,fin);reset(input);
    assign(output,fon);rewrite(output);
    read(n,P);
    for i:=1 to n do read(c[i].a,c[i].b);
    xuli;
close(input);close(output);
end.


Không có nhận xét nào:

Đăng nhận xét

Lưu ý: Chỉ thành viên của blog này mới được đăng nhận xét.