fork download
copy 
  1. #include <iostream>
  2. #include<cmath>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	// your code goes here
  7. 	int n,r;
  8.  
  9. 	scanf("%d %d", &n, &r);
  10.  
  11. 	int loc;
  12. 	scanf("%d", &loc);
  13.  
  14. 	int xy[loc+1][2],i,j;
  15.  
  16. 	for(i=0;i<loc; i++){
  17. 		scanf("%d %d" , &xy[i][0], &xy[i][1]);
  18. 	}
  19.  
  20. 	int s;
  21. 	scanf("%d", &s);
  22.  
  23. 	int xys[s+1][3];
  24.  
  25. 	for(i=0;i<s;i++){
  26. 		scanf("%d %d %d", &xys[i][0], &xys[i][1], &xys[i][2]);
  27. 	}
  28.  
  29. 	// precomputing distances
  30.  
  31. 	float dist[loc+1][s+1];
  32.  
  33. 	for(i=0; i < loc; i++){
  34. 		for(j=0; j <s; j++){
  35. 			float distx = abs(xys[j][0] - xy[i][0]);
  36. 			float disty = abs(xys[j][1] - xy[i][1]);
  37.  
  38. 			float d = (distx*distx) + (disty*disty);
  39. 			d = sqrt(d);
  40.  
  41. 			dist[i][j] = d;
  42.  
  43. 		}
  44. 	}
  45.  
  46. 	// consider all possible locations
  47.  
  48. 	long int tot = 1<<loc;
  49.  
  50. 	long int ans = 0;
  51.  
  52. 	bool visit[s+1];
  53.  
  54. 	// lest number with n set bits
  55. 	i = 1<<n;
  56. 	i -= 1;
  57.  
  58. 	while(i < tot){
  59.  
  60. 		int calc = 0;
  61.  
  62. 		// check which locations are considered in i
  63.  
  64. 		for(int l =0; l < s; l++)
  65. 			visit[l] = 0;
  66.  
  67.  
  68. 		for(j = 0; j < loc; j++ ){
  69.  
  70. 			if( (i&(1<<j)) ){
  71. 				// we are considering j'th location
  72.  
  73. 			for(int k = 0; k < s; k++){
  74.  
  75. 				float d = dist[j][k];
  76.  
  77. 				if( d <= r && visit[k] == 0){
  78. 				 		calc += xys[k][2];
  79. 						visit[k] = 1;
  80. 						//	cout<<k<<" ";
  81. 					}
  82. 				}
  83. 			}
  84. 		}
  85.  
  86. 	//	cout<<"Total : "<<calc<<endl;
  87. 		if( ans < calc )
  88. 			ans = calc;
  89.  
  90. 		// find the next higher number with same number of set bits
  91. 		int right = i&(-i);
  92. 		int next = i+right;
  93. 		int op = (i^next);
  94. 		op = op/right;
  95. 		op>>=2;
  96. 		i = next|op;
  97.  
  98. 	}
  99.  
  100. 	printf("%d\n",ans);
  101.  
  102. 	return 0;
  103. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
3 3 
5 
0 0 
1 6 
2 3 
6 6 
7 2 
8 
0 1 2 
0 5 3 
0 6 1 
1 0 1 
3 2 3 
3 6 2 
6 2 4 
8 6 3
stdout
copy 
17
https://ideone.com/kerT7s
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!