fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define MOD 1000000007
  5. #define M(x) (x % MOD + MOD )%MOD
  6. #define _mp make_pair
  7. #define _pb push_back
  8. #define ff first
  9. #define ss second
  10.  
  11. ll mul( ll x, ll y)
  12. { ll ans=1;
  13.   while(y>0)
  14.   { if(y&1)
  15.   	ans=(ans*x)%MOD;
  16.   	x=(x*x)%MOD;
  17.   	y/=2;
  18.   }
  19.  
  20.     return ans;
  21. };
  22.  
  23. //....................................................................................
  24. ll a[1005][1005],range[1005],c[1005],cnt[1005],vis[1005],Task[1005][2],work[1005][2];
  25. double a1[1005][1005];
  26. void utility(int n,int m){
  27. 	cout<<"Enter the co-Ordinates of the workers\n";
  28. 	for (int i=1;i<=n;i++)
  29. 		for (int j=0;j<2;j++)
  30. 			{
  31. 				cin>>work[i][j];			
  32. 			}
  33. 	cout<<"Enter the co-Ordinates of the Task\n";
  34. 	for (int i=1;i<=m;i++)
  35. 		for (int j=0;j<2;j++)
  36. 			{
  37. 				cin>>Task[i][j];			
  38. 			}
  39. 	double k;	
  40. 	for(int i=1;i<=n;i++)
  41. 	for(int j=1;j<=m;j++)
  42. 	{
  43. 		k=sqrt(pow((Task[j][1]-work[i][1]),2)+pow((Task[j][0]-work[i][0]),2));
  44. 		a1[i][j]=k;
  45. 		//cout<<k<<"\n";	
  46. 	}
  47. 	cout<<"Enter the Range of the Workers\n";
  48. 	for(int i=1;i<=n;i++)
  49. 	cin>>range[i];
  50.  
  51. }
  52.  
  53. int main()
  54. {   ll val,n,m,i,j;  // n is no. of workers , m is no. of tasks
  55.     cout<<"Enter no. of workers and no. of tasks ->\n";
  56. 	cin>>n>>m;
  57.  
  58.  
  59. 	utility(n,m);	
  60. 	cout<<"Enter the utility table for each worker ->\n";	
  61. 	for(i=1;i<=n;i++)
  62. 	for(j=1;j<=m;j++)
  63. 	cin>>a[i][j];  //  utility of a task by a specific worker
  64.  
  65. 	//cout<<"Enter the task access table for each worker ->\n";
  66. //	for(i=1;i<=n;i++){
  67. //	for(j=1;j<=m;j++)
  68. //	{ if (a1[i][j]<=range[i])
  69. //		val=1;
  70. //		else 
  71. //		val=0;
  72. //	cout <<val<<" ";
  73. //	  if(val==0)
  74. //	  a[i][j]=-1;   	
  75. //	}
  76. //	cout<<"\n";
  77. //	}            
  78.  
  79. 	cout<<"Enter the capacity of each worker ->\n";
  80. 	for(i=1;i<=n;i++)
  81. 	cin>>c[i];
  82.  
  83. 	cout<<"Optimised value will be ->\n";
  84. 	vector<set<pair<ll,ll> >  > v(1005);
  85.  
  86. 	for(i=1;i<=m;i++)
  87. 	for(j=1;j<=n;j++)
  88. 	if(a[j][i]!=-1)
  89. 	v[i].insert(_mp(a[j][i],j));
  90.  
  91. 	ll ans=0;
  92. 	pair<ll,ll> p;
  93.  
  94. 	vector<set<pair<ll,ll> > > vv(1005);
  95.  
  96.     for(i=1;i<=m;i++)
  97. 	{ if(!v[i].empty())
  98. 	  { p=*v[i].rbegin();
  99. 	  	v[i].erase(p);
  100. 	    ans+=p.ff;
  101. 	    ++cnt[p.ss];
  102. 	    vv[p.ss].insert(_mp(p.ff,i));
  103. 	  }
  104. 	}
  105.  
  106. 	for(i=1;i<=n;i++)
  107. 	while(cnt[i]>c[i])
  108. 	{ p=*vv[i].begin();
  109. 	  ans-=p.ff;
  110. 	  vv[i].erase(p);
  111. 	  vis[p.ss]=1;
  112. 	  --cnt[i];	
  113. 	}
  114.  
  115. 	for(i=1;i<=m;i++)
  116. 	if(vis[i]==1)
  117. 	{ while(!v[i].empty())
  118. 	  { p=*v[i].rbegin();
  119. 	  	v[i].erase(p);
  120.  
  121. 	  	if(cnt[p.ss]<c[p.ss])
  122. 	  	{ ++cnt[p.ss];
  123. 	  	  ans+=p.ff;	
  124. 		  break; 
  125. 		}
  126. 	  }	
  127. 	}
  128.  
  129. 	cout<<ans;	 
  130. 	return 0;
  131. }
Success #stdin #stdout 0s 31912KB
comments (?)
stdin
copy 
3 6
5 2
2 2
3 4
4 2
5 1
2 3
2 4
2 6
3 5
10
11
12
7 1 2 3 2 1 
5 1 1 2 1 2 
6 2 9 1 1 1
1
3
2
stdout
copy 
Enter no. of workers and no. of tasks ->
Enter the co-Ordinates of the workers
Enter the co-Ordinates of the Task
Enter the Range of the Workers
Enter the utility table for each worker ->
Enter the capacity of each worker ->
Optimised value will be ->
23
https://ideone.com/aTgrCK
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

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!