Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
9
Indexable
#include<iostream>

using namespace std;

int t,k,r,m,n,people,ans,cnt;
int restaurant[20][2], soli[100][3];
bool visited[20];
int checksoli[100];

bool isinside(int x, int y){
	int row=restaurant[x][0]-soli[y][0]; int c=restaurant[x][1]-soli[y][1];
	if(row*row+c*c<=r*r) return true;
	return false;
}

void bt(int dem){
	if(cnt==k){
		if(people>ans) ans=people;
	}
	if(dem==m) return;
	else{
		for(int i=0;i<2;i++){
			if(i==1){
				for(int j=0;j<n;j++){
					if(isinside(dem,j)) checksoli[j]++;
					if(checksoli[j]==1) people+=soli[j][2];
				}
				cnt++;
				bt(dem+1);
				for(int j=0;j<n;j++){
					if(isinside(dem,j)) checksoli[j]--;
					if(checksoli[j]==0) people-=soli[j][2];
				}
				cnt--;
			}
			else{
				bt(dem+1);
			}
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		cin >> k >> r;
		cin >> m;
		for(int i=0;i<m;i++){
			cin >> restaurant[i][0] >> restaurant[i][1]; 
			visited[i]=false;
		}
		cin >> n;
		for(int i=0;i<n;i++){
			cin >> soli[i][0] >> soli[i][1] >> soli[i][2];
			checksoli[i]=0;
		}
		cnt=0; ans=0;
		bt(0);
		cout << "#" << tc << " " << ans << endl;
	}


	return 0;
}
Editor is loading...
Leave a Comment