PIZZALOC - Pizza Location

Tác giả: skyvn97

Ngôn ngữ: C++

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

Download