PIZZALOC - Pizza Location
Tác giả: happyboy99x
Ngôn ngữ: C++
#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;
}