PIZZALOC - Pizza Location

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program PIZZALOC;
Const
  input  = '';
  output = '';
  maxn = 100;
  maxm = 20;
Type
  rec = record
    x,y: integer;
  end;
Var
  n,m,k,r,res,resmax: integer;
  s,e: array[1..maxn] of rec;
  num,es,curr: array[1..maxn] of integer;
  last: array[0..maxn] of integer;
  ser: array[1..maxm,1..maxn] of integer;
  free: array[1..maxm] of boolean;

Procedure init;
Var
  f: text;
  i: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, k, r);

  Readln(f, m);
  For i:= 1 to m do readln(f, s[i].x, s[i].y);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Read(f, e[i].x, e[i].y);
      Readln(f, num[i]);
    End;

  Close(f);
End;

Procedure gens;
Var
  i,j,dis: integer;
Begin
  Fillchar(es, sizeof(es), 0);
  For i:= 1 to m do
    For j:= 1 to n do
      Begin
        dis:= sqr(s[i].x - e[j].x) + sqr(s[i].y - e[j].y);
        If dis <= r * r then
          Begin
            inc(es[i]);
            ser[i,es[i]]:= j;
          End;
      End;

  Fillchar(free, sizeof(free), true);

  Fillchar(curr, sizeof(curr), 0);
  res:= 0;
  resmax:= 0;

  last[0]:= 0;
End;

Procedure attempt(i: integer);
Var
  j,ij: integer;
Begin
  For j:= last[i - 1] + 1 to m do if free[j] then
    Begin
      free[j]:= false;
      last[i]:= j;

      For ij:= 1 to es[j] do
        Begin
          If curr[ser[j,ij]] = 0 then res:= res + num[ser[j,ij]];
          inc(curr[ser[j,ij]]);
        End;

      If i = k then
        Begin
          If resmax < res then resmax:= res;
        End
      else attempt(i + 1);

      free[j]:= true;
      For ij:= 1 to es[j] do
        Begin
          dec(curr[ser[j,ij]]);
          If curr[ser[j,ij]] = 0 then res:= res - num[ser[j,ij]];
        End;
    End;
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    Writeln(f, resmax);
  Close(f);
End;

Begin
  init;
  gens;
  attempt(1);
  printresult;
End.

Download