fork download
  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
stdin
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
stdout
22