PIZZALOC - Pizza Location

Tác giả: ladpro98

Ngôn ngữ: Pascal

program pizzaloc;
uses    math;
type    pizzares=record
                x,y:longint;
        end;
        house=record
                x,y,s:longint;
        end;
        arr=array[0..11] of longint;
const   lim=10;
        maxn=123;
        maxm=21;
        fi='';
var     pos:array[1..maxn] of pizzares;
        a:array[1..maxn] of house;
        bit:array[0..maxn,0..maxn] of longint;
        p:array[0..maxn,0..1 shl lim] of longint;
        cs:arr;
        k,r,m,n,res,mp:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,k,r);
        readln(inp,m);
        for i:=1 to m do
        readln(inp,pos[i].x,pos[i].y);
        readln(inp,n);
        for i:=1 to n do
        readln(inp,a[i].x,a[i].y,a[i].s);
        close(inp);
end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

procedure init;
var     k,i,j:longint;
begin
        r:=sqr(r);
        mp:=n div lim;
        for i:=1 to m do
        begin
                for j:=1 to n do
                if (r>=(sqr(pos[i].x-a[j].x)+sqr(pos[i].y-a[j].y))) then
                begin
                        if j mod lim<>0 then
                        inc(bit[i,j div lim],1 shl (j mod lim-1))
                        else
                        inc(bit[i,j div lim-1],1 shl (lim-1));
                end;
        end;
        for k:=0 to n div lim do
        for i:=0 to 1 shl lim-1 do
        begin
                for j:=1 to lim do
                if getbit(i,j)=1 then
                inc(p[k,i],a[j+k*lim].s);
        end;
end;

procedure back(i,c:longint; s:arr);
var     j,t:longint;
begin
        if (c>=k) then
        begin
                t:=0;
                for j:=0 to mp do
                inc(t,p[j,s[j]]);
                res:=max(res,t);
                exit;
        end;
        if i>m then exit;
        if (k-c)<=(m-i) then back(i+1,c,s);
        for j:=0 to mp do
        s[j]:=s[j] or bit[i,j];
        back(i+1,c+1,s);
end;

begin
        input;
        init;
        back(1,0,cs);
        write(res);
end.

Download