BARICAVN - BARICA
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program BARICAVN;
uses math;
const
input = '';
output = '';
maxn = 300000;
maxt = 100000;
type
rec = record
x,y,val,pos: integer;
end;
var
a: array[1..maxn] of rec;
maxx,maxy: array[0..maxt] of integer;
n,k: integer;
procedure init;
var
f: text;
i: integer;
begin
assign(f, input);
reset(f);
readln(f, n, k);
for i := 1 to n do
begin
readln(f, a[i].x,a[i].y,a[i].val);
a[i].pos := i;
end;
close(f);
end;
procedure swap(var u,v: rec);
var
z: rec;
begin
z := u; u := v; v := z;
end;
function lower(u,v: rec): boolean;
begin
lower := (u.x < v.x) or ((u.x = v.x) and (u.y < v.y));
end;
procedure quicksort;
procedure par(l,h: integer);
var
i,j: integer;
p: rec;
begin
if l >= h then exit;
i := l; j := h; p := a[random(h - l + 1) + l];
repeat
while lower(a[i],p) do inc(i);
while lower(p,a[j]) do dec(j);
if i <= j then
begin
if i < j then swap(a[i],a[j]);
inc(i);
dec(j);
end;
until i > j;
par(l,j);
par(i,h);
end;
begin
par(1,n);
end;
procedure solve;
var
f: text;
i,t: integer;
begin
for i := 0 to maxt do
begin
maxx[i] := -maxn;
maxy[i] := -maxn;
end;
i := 1;
while a[i].pos <> 1 do inc(i);
maxx[a[i].x] := a[i].val;
maxy[a[i].y] := a[i].val;
repeat
inc(i);
t := max(maxx[a[i].x],maxy[a[i].y]);
if t >= k then t := t - k + a[i].val;
if maxx[a[i].x] < t then maxx[a[i].x] := t;
if maxy[a[i].y] < t then maxy[a[i].y] := t;
until a[i].pos = n;
assign(f, output);
rewrite(f);
writeln(f, t);
close(f);
end;
begin
init;
quicksort;
solve;
end.