BARICAVN - BARICA

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=100010;
var n,k:longint;
    x,y,a,d,f:array[1..maxn] of longint;
    maxcol:array[0..maxn] of longint;

procedure rf;
var i:longint;
begin
     read(n,k);
     for i:=1 to n do
     begin
          read(x[i],y[i],a[i]);
          d[i]:=i;
     end;
end;

procedure sort(l,r:longint);
var i,j,t,u,v:longint;
begin
     i:=l; j:=r; t:=x[(i+j) shr 1]; v:=y[(i+j) shr 1];
     repeat
           while (x[i]<t) or ((x[i]=t) and (y[i]<v)) do i:=i+1;
           while (x[j]>t) or ((x[j]=t) and (y[j]>v)) do j:=j-1;
           if i<=j then
           begin
                u:=d[i]; d[i]:=d[j]; d[j]:=u;
                u:=x[i]; x[i]:=x[j]; x[j]:=u;
                u:=y[i]; y[i]:=y[j]; y[j]:=u;
                u:=a[i]; a[i]:=a[j]; a[j]:=u;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function max(u,v:longint):longint;
begin
     if u>v then max:=u else max:=v;
end;

procedure pr;
var i,t,u,maxrow:longint;
begin
     sort(1,n);
     for i:=1 to n do f[i]:=-1;
     for i:=0 to maxn div 3 do maxcol[i]:=-1;
     for t:=1 to n do
         if d[t]=1 then break;
     f[t]:=a[t]; maxcol[y[t]]:=a[t]; maxrow:=a[t]; inc(t);
     while true do
     begin
          if x[t]=x[t-1] then
          begin
               if maxrow>=k then
                  f[t]:=max(f[t],maxrow-k+a[t]);
          end;
          if maxcol[y[t]]>=k then
             f[t]:=max(f[t],maxcol[y[t]]-k+a[t]);
          if x[t]=x[t-1] then maxrow:=max(maxrow,f[t])
          else maxrow:=f[t];
          maxcol[y[t]]:=max(maxcol[y[t]],f[t]);
          if d[t]=n then break;
          t:=t+1;
     end;
     writeln(f[t]);
end;

begin
     rf;
     pr;
end.

Download