PIZZALOC - Pizza Location

Tác giả: flashmt

Ngôn ngữ: Pascal

type ar=array[1..100] of boolean;
var n,k,m,re,r:longint;
    a:array[1..20,0..1] of longint;
    b:array[1..100,0..2] of longint;
    d:array[1..100,1..20] of boolean;
    f:array[1..20] of longint;
    c,e:ar;

procedure rf;
var i:longint;
begin
     readln(k,r);
     readln(m);
     for i:=1 to m do readln(a[i,0],a[i,1]);
     readln(n);
     for i:=1 to n do readln(b[i,0],b[i,1],b[i,2]);
end;

procedure init;
var i,j,t:longint;
begin
     for j:=1 to m do
         for i:=1 to n do
             if sqr(a[j,0]-b[i,0])+sqr(a[j,1]-b[i,1])<=r*r then
             begin
                  d[i,j]:=true;
                  inc(f[j],b[i,2]);
             end;
end;

procedure att(i,j:longint;var s:longint;e:ar);
var p,q,t:longint;
begin
     if (i>k) or (j>m) then
     begin
          if s>re then re:=s;
          exit;
     end;
     for p:=j to m-k+i do
     begin
          if (i=k) and (f[p]+s<=re) then continue;
          t:=0;
          fillchar(e,sizeof(e),false);
          for q:=1 to n do
              if (not c[q]) and d[q,p] then
              begin
                   t:=t+b[q,2];
                   c[q]:=true;
                   e[q]:=true;
              end;
          s:=s+t;
          att(i+1,p+1,s,e);
          for q:=1 to n do
              if e[q] then c[q]:=false;
          s:=s-t;
     end;
end;

procedure pr;
var i,j,s:longint;
begin
     init;
     re:=0; s:=0;
     att(1,1,s,e); 
     writeln(re);
end;

begin
     rf;
     pr;
end.

Download