fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std; 
  4.  
  5. #define mp make_pair
  6. typedef pair<int, int> pii;
  7.  
  8. vector<int> points;
  9. long long easy;
  10. long long ans;
  11. long long lt[110000];
  12. long long rt[110000];
  13. int n, k;
  14. vector< pii > bridge;
  15.  
  16. bool compara(pii a, pii b) {
  17. 	return a.first + a.second < b.first + b.second;
  18. }
  19.  
  20. template<class T> 
  21. void calc(T it, T ed, long long *arr) {
  22. 	multiset<int> sm;
  23. 	multiset<int> bg;
  24.  
  25. 	long long ssm = 0;
  26. 	long long sbg = 0;
  27.  
  28. 	int c = 0;
  29. 	arr[c++] = 0;
  30.  
  31. 	while (it != ed) {
  32. 		sm.insert(it->first);
  33. 		ssm += it->first;
  34. 		bg.insert(it->second);
  35. 		sbg += it->second;
  36.  
  37. 		while (*sm.rbegin() > *bg.begin()) {
  38. 			sbg += *sm.rbegin() - *bg.begin();
  39. 			ssm += *bg.begin() - *sm.rbegin();
  40. 			bg.insert(*sm.rbegin());
  41. 			sm.insert(*bg.begin());
  42. 			bg.erase(bg.begin());
  43. 			sm.erase(--sm.end());
  44. 		}
  45.  
  46. 		arr[c++] = sbg - ssm;
  47. 		it++;
  48. 	}
  49. }
  50.  
  51. int main() {
  52. 	scanf("%d %d", &k, &n);
  53.  
  54. 	for (int i = 0; i < n; i++) {
  55. 		char t1, t2;
  56. 		int x, y;
  57. 		scanf(" %c %d %c %d", &t1, &x, &t2, &y);
  58. 		if (t1 == t2) easy += abs(y-x);
  59. 		else bridge.push_back(mp(x, y));
  60. 	}
  61.  
  62. 	sort(bridge.begin(), bridge.end(), compara);
  63.  
  64. 	calc(bridge.begin(), bridge.end(), lt); // prefixes
  65. 	calc(bridge.rbegin(), bridge.rend(), rt); // suffixes
  66.  
  67. 	n = bridge.size();
  68.  
  69. 	if (k == 1) {
  70. 		ans = rt[n];
  71. 	}
  72. 	else {
  73. 		ans = 1000000000000000000LL;
  74. 		for (int in_lt = 0; in_lt <= n; in_lt++) {
  75. 			ans = min(ans, lt[in_lt] + rt[n - in_lt]);
  76. 		}
  77. 	}
  78.  
  79. 	printf("%lld\n", easy + ans + n);
  80. }
Success #stdin #stdout 0s 4996KB
comments (?)
stdin
copy 
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
stdout
copy 
22
https://ideone.com/plXDD0
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!