fork download
  1. #include <bits/stdc++.h>
  2. // #include "bits/stdc++.h"
  3.  
  4. #ifndef bhupixb
  5. #define var(...)
  6. #define stl(...)
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12.  
  13. #define rep(i, a, b) for (int i = a; i <= (int)b; ++i)
  14.  
  15. int w, n;
  16.  
  17. void solve() {
  18. cin >> w >> n;
  19. map<int,int> mp;
  20. rep(i,1,w) {
  21. int x;
  22. cin >> x;
  23. mp[x]++;
  24. }
  25. vector<array<int,2>> a;
  26. for (auto it: mp) {
  27. a.push_back({it.first, it.second});
  28. }
  29. int N = a.size();
  30. const int inf = 1e15;
  31. vector<int> dp(N, inf);
  32. vector<int> pref_sum(N), cnt(N);
  33. for (int i = 0; i < N; ++i) {
  34. pref_sum[i] = a[i][0] * a[i][1];
  35. cnt[i] = a[i][1];
  36. if (i > 0) {
  37. cnt[i] += cnt[i-1];
  38. pref_sum[i] += pref_sum[i - 1];
  39. }
  40.  
  41. }
  42. auto getLR = [&] (int l, int r, vector<int> &pref_sum) {
  43. if (l > r) return 0LL;
  44. if (!(l >= 0 and r < N)) {
  45. var(l, r);
  46. exit(0);
  47. }
  48. if (!l) {
  49. return pref_sum[r];
  50. }
  51. return pref_sum[r] - pref_sum[l-1];
  52. };
  53. int res = 1e18;
  54. for (int i = 0; i < N; ++i) {
  55. int ans = 0;
  56. {
  57. int lo = 0, hi = i - 1;
  58. int lastJ = i;
  59. while (lo <= hi) {
  60. int mid = (lo + hi) / 2;
  61. int j = mid;
  62. int diff = a[i][0] - a[j][0];
  63. int cnt1 = a[j][1];
  64. int seedha = diff * a[j][1];
  65. int ulta = ((n - a[i][0]) + (a[j][0])) * cnt1;
  66. if (seedha <= ulta) {
  67. hi = mid - 1;
  68. lastJ = mid;
  69. }
  70. else {
  71. lo = mid + 1;
  72. }
  73. }
  74. if (lastJ != i) {
  75. int ct = getLR(lastJ, i-1, cnt);
  76. int sum = getLR(lastJ, i - 1, pref_sum);
  77. int ok = a[i][0] * ct - sum;
  78. ans += ok;
  79. }
  80. if (lastJ > 0) {
  81. int j = lastJ - 1;
  82. int ct = getLR(0, j, cnt);
  83. int ok = 0;
  84. ok += ct * (n - a[i][0]);
  85. ok += getLR(0, j, pref_sum);
  86. var(ok);
  87. ans += ok;
  88. }
  89. }
  90. {
  91. int lo = i + 1, hi = N - 1;
  92. int lastJ = i;
  93. while (lo <= hi) {
  94. int mid = (lo + hi) / 2;
  95. int j = mid;
  96. int diff = a[j][0] - a[i][0];
  97. int seedha = diff * a[j][1];
  98. int ulta = (n - a[j][0]) * a[j][1] + (a[i][0]) * a[j][1];
  99. if (seedha <= ulta) {
  100. lastJ = mid;
  101. lo = mid + 1;
  102. }
  103. else {
  104. hi = mid - 1;
  105. }
  106. }
  107. if (lastJ != i) {
  108. int ct = getLR(i+1, lastJ, cnt);
  109. int sum = getLR(i+1, lastJ, pref_sum);
  110. int ok = sum - ct * a[i][0];
  111. ans += ok;
  112. }
  113. if (lastJ < N - 1) {
  114. int j = lastJ + 1;
  115. int ct = getLR(j, N - 1, cnt);
  116. int sum = getLR(j, N - 1, pref_sum);
  117. int ok = 0;
  118. ok += n * ct - sum + ct * a[i][0];
  119. ans += ok;
  120. }
  121. }
  122. res = min(ans, res);
  123. }
  124. cout << res << '\n';
  125. }
  126.  
  127. // #define single_test
  128.  
  129. signed main() {
  130. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  131. int t = 1;
  132. #ifndef single_test
  133. cin >> t;
  134. #endif
  135. for (int i = 1; i <= t; ++i) {
  136. cout << "Case #" << i << ": ";
  137. solve();
  138. }
  139. return 0;
  140. }
Success #stdin #stdout 0.01s 4532KB
stdin
Standard input is empty
stdout
Case #1: 1000000000000000000