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;
}

Download