fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. const int P=400,T=200;
  4. int can[T][P];
  5. int at[P],got[T],tried[T];
  6. bool pick(int txi,int p){
  7. 	if(tried[txi])return false;
  8. 	tried[txi]=1;
  9. 	for(int i=0;i<p;i++){
  10. 		int x = at[i];
  11. 		if(can[txi][i]){
  12. 			if(x==-1){
  13. 				at[i] = txi;
  14. 				got[txi] = 1;
  15. 				return true;
  16. 			}
  17. 			if(pick(x,p)){
  18. 				at[i] = txi;
  19. 				got[txi] = 1;
  20. 				return true;
  21. 			}
  22. 		}
  23. 	}
  24. 	return false;
  25. }
  26. struct person{
  27. 	int x, y;	
  28. };
  29. struct taxi{
  30. 	int x, y;	
  31.  
  32. };
  33. int f(int a){
  34. 	if(a<0)return -a;
  35. 	return a;
  36. }
  37. bool reach(taxi t,person p,int d){
  38. 	long long dist = f(t.x-p.x) + f(t.y-p.y);
  39. 	dist*=200;
  40. 	if(dist<=d)return true;
  41. 	return false;
  42. }
  43. int main() {
  44. 	// your code goes here
  45. 	int T,p,t,j,i,s,c;
  46. 	cin>>T;
  47. 	while(T--){
  48. 		cin>>p>>t>>s>>c;
  49. 		person Y[p];
  50. 		taxi X[t];
  51. 		for(i=0;i<p;i++){
  52. 			cin>>Y[i].x>>Y[i].y;
  53. 			at[i] = -1;
  54. 		}
  55. 		for(i=0;i<t;i++){
  56. 			cin>>X[i].x>>X[i].y;
  57. 			got[i] = 0;
  58. 		}
  59.  
  60. 		for(i=0;i<t;i++)
  61. 		for(j=0;j<p;j++)
  62. 			can[i][j]=0;
  63.  
  64. 		for(i=0;i<t;i++)
  65. 		for(j=0;j<p;j++)
  66. 			if(reach(X[i],Y[j],c*s))
  67. 				can[i][j]=1;
  68. 		int ans = 0;
  69. 		for(i=0;i<t;i++){
  70. 			for(j=0;j<t;j++)
  71. 				tried[j]=0;
  72. 			if(!got[i] && pick(i,p))ans++;
  73. 		}
  74. 		cout<<ans<<endl;
  75.  
  76. 	}
  77. 	return 0;
  78. }
Runtime error #stdin #stdout 0s 3056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jXAem3
problem TAXI, based on SPOJ submission 14928246 (C++ 4.3.2), 2015-08-19 15:25:23
language:
C++ 4.3.2 (gcc-4.3.2)
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!