PIZZALOC - Pizza Location

Tác giả: RR

Ngôn ngữ: C++

#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 mask[MAXN],S;

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)
            mask[i]+=1L<<(j-1);
    }
}

void update() {
    long sum=0;
    FOR(i,1,n)
        if (S&mask[i]) sum+=s[i];
    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;
}

Download