Editorial for Pizza Location

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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
for i:=1 to m do readln(a[i,0],a[i,1]);
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.


Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

#define M 20+5
#define N 100+5

int a[M][N];
int rx[M], ry[M], hx[N], hy[N], p[N]; //restaurant x, y, house x, y, people
int k, r, m, n, inRange[N], now, res;

inline int sqr(int x) { return x*x; }

void init() {
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
if(sqr(hx[j]-rx[i]) + sqr(hy[j]-ry[i]) <= r)
a[i][++a[i][0]] = j;
}

void enter() {
scanf("%d%d%d",&k,&r,&m); r *= r;
for(int i = 0; i < m; ++i) scanf("%d%d",rx+i,ry+i);
scanf("%d",&n);
for(int i = 0; i < n; ++i) scanf("%d%d%d",hx+i,hy+i,p+i);
}

void backtrack(int q, int x) {
if(k-q > m-x) return;
if(q == k) res = max(now, res);
else for(int i = x; i < m; ++i) {
for(int j = 1; j <= a[i][0]; ++j)
if(inRange[a[i][j]]++ == 0) now += p[a[i][j]];
backtrack(q+1, i+1);
for(int j = 1; j <= a[i][0]; ++j)
if(--inRange[a[i][j]] == 0) now -= p[a[i][j]];
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
enter();
init();
backtrack(0, 0);
printf("%d\n", res);
return 0;
}


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);
for i:=1 to m do
for i:=1 to n do
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.


Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 111
#define FOR(i,a,b) for(long i=a; i<=b; i++)
using namespace std;

long k,r,m,x[MAXN],y[MAXN],n,x2[MAXN],y2[MAXN],s[MAXN],res,kq[MAXN];

long sqr(long u) {
return u*u;
}

void inp() {
scanf("%ld %ld %ld",&k,&r,&m);
FOR(i,1,m) scanf("%ld %ld",&x[i],&y[i]);

scanf("%ld",&n);
FOR(i,1,n) scanf("%ld %ld %ld ",&x2[i],&y2[i],&s[i]);

FOR(i,1,n) {
FOR(j,1,m)
if (sqr(x2[i]-x[j])+sqr(y2[i]-y[j])<=r*r)
}
}

void update() {
long sum=0;
FOR(i,1,n)
res=max(res,sum);
}

void duyet(long i) {
if (i>k) {
update();
return ;
}

FOR(j,kq[i-1]+1,m-k+i) {
S+=1L<<(j-1);
kq[i]=j;
duyet(i+1);
S-=1L<<(j-1);
}
}

void solve() {
duyet(1);
printf("%ld\n",res);
}

int main() {
inp();
solve();
return 0;
}


Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

{
int x,y;
};

struct cuahang
{
public:
int sch,a[101];
};

int main()
{
//freopen("PIZZALOC.in","r",stdin);
int k,r,m,n,nguoi[101];
cuahang  ch[21];
scanf("%d %d",&k,&r);
scanf("%d",&m);

for(int i = 1;i<=m;i++)
{
//printf("1\n");
//ch[i].sch = 0;
scanf("%d %d",&A[i].x,&A[i].y);
}
// printf("2\n");
scanf("%d",&n);
for(int i = 1;i<=n ; i++)
scanf("%d %d %d",&B[i].x,&B[i].y,&nguoi[i]);
for(int i = 1;i<=m;i++)
{
// printf("3\n");
ch[i].sch = 0;
// printf("4\n");
for(int j = 1;j<=n;j++)

if((A[i].x-B[j].x)*(A[i].x-B[j].x)+(A[i].y-B[j].y)*(A[i].y-B[j].y)<= r*r)
{
ch[i].sch++;
ch[i].a[ch[i].sch] = j;
}
}

int u[k+1],flag[101],KQ = 0;
for(int i = 1;i<=k;i++)
u[i] = i;

while(true)
{
//for(int i = 1;i<=k;i++) printf("%d ",u[i]);
//printf("\n");
int max = 0;
for(int i = 1 ;i<=n;i++)
flag[i] = 0;
for(int i = 1;i<=k;i++)
for(int j = 1;j<=ch[u[i]].sch;j++)
if(flag[ch[u[i]].a[j]]==0)
{
flag[ch[u[i]].a[j]]=1;
max = max + nguoi[ch[u[i]].a[j]];
}
// printf("_____%d____\n",max);
if(max>KQ)
KQ = max;
if(u[k]<m)
u[k]++;
else
{
int fl = k-1;
while(fl>0)
{
if(u[fl]+1!=u[fl+1])
break;
fl--;
}
if(fl==0)
break;
else
{
u[fl]++;
for(int i = fl+1;i<=k;i++)
u[i] = u[i-1]+1;
}
}
}
printf("%d",KQ);
//getch();
}


Code mẫu của ll931110

{\$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);

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

For i:= 1 to n do
Begin
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.


Code mẫu của skyvn97

#include<stdio.h>
#define MAX   250
struct pos
{
long x;
long y;
};
int k,n,m,r,sum,b;
pos p[MAX];
pos h[MAX];
int s[MAX];
int sou[MAX];
bool c[MAX];
bool go[MAX][MAX];
void init(void)
{
scanf("%d",&k);
scanf("%d",&r);
scanf("%d",&m);
int i,j;
for (i=1;i<=m;i=i+1)
{
scanf("%ld",&p[i].x);
scanf("%ld",&p[i].y);
}
scanf("%d",&n);
for (i=1;i<=n;i=i+1)
{
scanf("%ld",&h[i].x);
scanf("%ld",&h[i].y);
scanf("%d",&s[i]);
}
for (i=1;i<=m;i=i+1)
for (j=1;j<=n;j=j+1)
{
if ((p[i].x-h[j].x)*(p[i].x-h[j].x)+(p[i].y-h[j].y)*(p[i].y-h[j].y)<=r*r) go[i][j]=true;
else go[i][j]=false;
}
for (i=1;i<=n;i=i+1) c[i]=false;
sou[0]=0;
b=0;
}
void update(void)
{
if (sum<=b) return;
b=sum;
}
void btrk(int t)
{
int i,j,l;
int tmp[MAX];
for (i=sou[t-1]+1;i+k-t<=m;i=i+1)
{
sou[t]=i;
l=0;
for (j=1;j<=n;j=j+1)
{
if ((go[i][j]) && (!c[j]))
{
l=l+1;
c[j]=true;
tmp[l]=j;
sum=sum+s[j];
}
}
if (t==k) update();
else btrk(t+1);
for (j=1;j<=l;j=j+1)
{
c[tmp[j]]=false;
sum=sum-s[tmp[j]];
}
}
}
int main(void)
{
init();
btrk(1);
printf("%d",b);
}