fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll maxn=100000, maxx=1000000001;
  5. typedef vector<ll> vi;
  6. typedef pair<ll,ll> pi;
  7. typedef pair<ll,pi> pii;
  8. typedef vector<pi> vii;
  9.  
  10. #define fi first
  11. #define sc second
  12. #define mp make_pair
  13. #define pb push_back
  14.  
  15. ll k,n;
  16. string buf,bufx;
  17. ll x, y;
  18. vi dict;
  19. ll sum[2*maxn+10];
  20. ll gege;
  21.  
  22. int main(){
  23. 	ios_base::sync_with_stdio(false);
  24. 	gege=0;
  25.  
  26. 	cin >> k >> n;
  27. 	if (k==1){
  28. 		for(int i=0;i<n;i++){
  29. 			cin >> buf >> x >> bufx >> y;
  30. 			if (buf==bufx) {
  31. 				gege+= labs(x-y);
  32. 			}
  33. 			else {
  34. 				dict.pb(x); dict.pb(y);
  35. 			}
  36. 		}
  37.  
  38. 		sort(dict.begin(),dict.end());
  39. 		for(int i=0;i<dict.size();i++){
  40. 			sum[i]=(i==0?0:sum[i-1])+dict[i];
  41. 		}
  42.  
  43. 		ll ans = LONG_LONG_MAX;
  44.  
  45. 		for(int i=0;i<dict.size();i++){
  46. 			ans =min(ans,dict[i]*(i+1)-sum[i]+sum[dict.size()-1]-sum[i]-dict[i]*(ll(dict.size())-i-1));
  47. 			//cout << dict[i] <<" " << dict[i]*(i+1)-sum[i]+sum[dict.size()-1]-sum[i]-dict[i]*(ll(dict.size())-i-1) << "\n";
  48. 		}
  49. 		if (ans==LONG_LONG_MAX) ans=0;
  50. 		cout << ans+gege+dict.size()/2 << "\n";
  51. 		return 0;
  52. 	}
  53. 	else{
  54. 		vii dic;
  55. 		for(int i=0;i<n;i++){
  56. 			cin >> buf >> x >> bufx >> y;
  57. 			if (buf==bufx){
  58. 				gege+=labs(x-y);
  59. 			}
  60. 			else{
  61. 				dic.pb(mp(x,y));
  62. 				dict.pb(x); dict.pb(y);
  63. 			}
  64. 		}
  65.  
  66. 		sort(dict.begin(),dict.end());
  67. 		ll ans = LONG_LONG_MAX, semen;
  68.  
  69. 		for(int i=0;i<dict.size();i++){
  70. 			ll l = 0, r = 1000000001;
  71. 			ll mid1,mid2,mid3,semen1,semen2,semen3;
  72. 			while(l<r){
  73. 				mid1=l+(r-l)/3; mid2=(l+(r-l)*2/3); mid3 = (l+r)/2;
  74.  
  75. 				semen1=0,semen2=0,semen3=0;
  76. 				for(int k=0;k<dic.size();k++){
  77. 					semen1+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid1)+labs(dic[k].sc-mid1));
  78. 					semen2+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid2)+labs(dic[k].sc-mid2));		
  79. 					semen3+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-mid3)+labs(dic[k].sc-mid3));		
  80. 				}
  81. 				if (semen1>semen3&&semen2>semen3){
  82. 					l=mid1; r=mid2;
  83. 				}
  84. 				else if (semen1>semen3&&semen2<semen3){
  85. 					l=mid1;
  86. 				}
  87. 				else{
  88. 					r=mid2;
  89. 				}
  90.  
  91. 				ans = min(ans,min(semen1,min(semen3,semen2)));
  92. 		//		cout << dict[l] << " " << dict[r]<<"\n";
  93. 			//	cout << l << " dan " << r << " jadinya " << ans << "\n";
  94.  
  95. 			}
  96. 			semen = 0;
  97. 			for(int k=0;k<dic.size();k++){
  98. 					semen+=min(labs(dic[k].fi-dict[i])+labs(dic[k].sc-dict[i]),labs(dic[k].fi-l)+labs(dic[k].sc-l));
  99. 			}
  100. 			ans=min(semen,ans);
  101. 		}
  102. 		if (ans==LONG_LONG_MAX) ans=0;
  103. 		cout << ans + gege+dict.size()/2 << "\n";
  104. 	}
  105. }
Success #stdin #stdout 0s 4844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/3hDpwD
language:
C++ (gcc 8.3)
created:
9 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!