BARICAVN - BARICA
Tác giả: ladpro98
Ngôn ngữ: Pascal
program baricavn;//dp
uses math;
type e=record
x,y,p,s:longint;
end;
const maxn=300005;
maxV=100005;
fi='';
var a:array[1..maxn] of e;
maxCol,maxRow:array[0..maxV] of longint;
n,k:longint;
procedure input;
var inp:text;
i:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,n,k);
for i:=1 to n do
begin
readln(inp,a[i].x,a[i].y,a[i].s);
a[i].p:=i;
end;
close(inp);
end;
procedure swap(i,j:longint);
var t:e;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure sort(l,r:longint);
var i,j:longint;
p:e;
begin
if l>=r then exit;
i:=l;j:=r;
p:=a[random(r-l+1)+l];
repeat
while (a[i].x<p.x) or ((a[i].x=p.x) and (a[i].y<p.y)) do inc(i);
while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].y>p.y)) do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);
dec(j);
end;
until i>j;
sort(l,j);
sort(i,r);
end;
procedure dp;
var j,i,t,lx,ly:longint;
begin
for j:=1 to n do
if a[j].p=1 then
begin
maxRow[a[j].x]:=a[j].s;
maxCol[a[j].y]:=a[j].s;
lx:=a[j].x;ly:=a[j].y;
for i:=j+1 to n do
if (a[i].x>=lx) and (a[i].y>=ly) then
if max(maxRow[a[i].x],maxCol[a[i].y])>=k then
begin
t:=max(maxRow[a[i].x],maxCol[a[i].y])-k+a[i].s;
if a[i].p=n then
begin
writeln(t);
exit;
end;
maxRow[a[i].x]:=max(maxRow[a[i].x],t);
maxCol[a[i].y]:=max(maxCol[a[i].y],t);
end;
end;
end;
begin
input;
sort(1,n);
dp;
end.