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.

Download