fork download
copy 
  1. #include <iostream>
  2. #include<vector>
  3. #include<cmath>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	// your code goes here
  8. 	int n,r;
  9.  
  10. 	scanf("%d %d", &n, &r);
  11.  
  12. 	int loc;
  13. 	scanf("%d", &loc);
  14.  
  15. 	int xy[loc+1][2],i,j;
  16.  
  17. 	for(i=0;i<loc; i++){
  18. 		scanf("%d %d" , &xy[i][0], &xy[i][1]);
  19. 	}
  20.  
  21. 	int s;
  22. 	scanf("%d", &s);
  23.  
  24. 	int xys[s+1][3];
  25.  
  26. 	for(i=0;i<s;i++){
  27. 		scanf("%d %d %d", &xys[i][0], &xys[i][1], &xys[i][2]);
  28. 	}
  29.  
  30. 	// precomputing distances
  31.  
  32. 	vector<int> vec[loc+1];
  33.  
  34. 	for(i=0; i < loc; i++){
  35.  
  36. 		for(j=0; j <s; j++){
  37. 			float distx = abs(xys[j][0] - xy[i][0]);
  38. 			float disty = abs(xys[j][1] - xy[i][1]);
  39.  
  40. 			float d = (distx*distx) + (disty*disty);
  41. 			d = sqrt(d);
  42.  
  43. 			if( d <= r){
  44. 				vec[i].push_back(j);
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	// consider all possible locations
  50.  
  51. 	long int tot = 1<<loc;
  52.  
  53. 	long int ans = 0;
  54.  
  55. 	bool visit[s+1];
  56.  
  57. 	// least number with n set bits
  58. 	i = 1<<n;
  59. 	i -= 1;
  60.  
  61. 	while(i < tot){
  62.  
  63. 		int calc = 0;
  64.  
  65. 		for(j=0;j<s; j++)
  66. 			visit[j] = 0;
  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< vec[j].size(); k++ ){
  74. 					if( visit[vec[j][k]] == 0){
  75. 						calc += xys[vec[j][k]][2];
  76. 						visit[vec[j][k]] = 1;
  77. 					}
  78. 				}
  79.  
  80. 			}
  81. 		}
  82.  
  83. 	//	cout<<"Total : "<<calc<<endl;
  84. 		if( ans < calc )
  85. 			ans = calc;
  86.  
  87. 		// find the next higher number with same number of set bits
  88. 		int right = i&(-i);
  89. 		int next = i+right;
  90. 		int op = (i^next);
  91. 		op = op/right;
  92. 		op>>=2;
  93. 		i = next|op;
  94.  
  95. 	}
  96.  
  97. 	printf("%d\n",ans);
  98.  
  99. 	return 0;
  100. }
Success #stdin #stdout 0s 3416KB
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/bhjTYZ
Spoj problem PIZZALOC
language:
C++14 (gcc 8.3)
created:
9 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!