fork download
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define Waimai ios::sync_with_stdio(false),cin.tie(0)
  7. #define FOR(x,a,b) for(int x=a;x<=b;x++)
  8. #define pb emplace_back
  9. #define F first
  10. #define S second
  11.  
  12. const int SIZE = 3e5 + 5;
  13.  
  14. struct Seg {int pos, l, r;};
  15.  
  16. int n, k, penalty;
  17. int a[SIZE], pre[SIZE];
  18. pair<int, int> dp[SIZE];
  19. deque<Seg> st;
  20.  
  21. int dis (int l, int r) {
  22. int mid = (l + r) / 2, ldis, rdis;
  23. ldis = (mid - l + 1) * a[mid] - (pre[mid] - pre[l - 1]);
  24. rdis = (pre[r] - pre[mid - 1]) - (r - mid + 1) * a[mid];
  25. return ldis + rdis;
  26. }
  27.  
  28. pair<int, int> cal (int l, int r) {
  29. return {dp[l].F + dis (l + 1, r) + penalty, dp[l].S + 1};
  30. }
  31.  
  32. bool ok (int p) {
  33. penalty = p;
  34. st.clear();
  35. st.push_back ({0, 1, n});
  36. FOR (i, 1, n) {
  37. while (st.size() && st[0].r < i) {
  38. st.pop_front();
  39. }
  40. dp[i] = cal (st[0].pos, i);
  41. while (st.size() && cal (i, st.back().l) <= cal (st.back().pos, st.back().l)) {
  42. st.pop_back();
  43. }
  44. if (!st.size()) {
  45. st.push_back ({i, i + 1, n});
  46. } else if (cal (i, st.back().r) >= cal (st.back().pos, st.back().r)) {
  47. if (st.back().r != n) {
  48. st.push_back ({i, st.back().r + 1, n});
  49. }
  50. } else {
  51. auto [pos, l, r] = st.back();
  52. while (l < r) {
  53. int mid = (l + r) / 2;
  54. if (cal (i, mid) > cal (pos, mid)) {
  55. l = mid + 1;
  56. } else {
  57. r = mid;
  58. }
  59. }
  60. st[st.size() - 1].r = l - 1;
  61. st.push_back ({i, l, n});
  62. }
  63. }
  64. return dp[n].S <= k;
  65. }
  66.  
  67. void solve() {
  68. cin >> n >> k;
  69. FOR (i, 1, n) cin >> a[i];
  70. sort (a + 1, a + n + 1);
  71. FOR (i, 1, n) pre[i] = pre[i - 1] + a[i];
  72. int l = 0, r = 5e10;
  73. while (l < r) {
  74. int mid = (l + r) / 2;
  75. if (ok (mid)) {
  76. r = mid;
  77. } else {
  78. l = mid + 1;
  79. }
  80. }
  81. ok (l);
  82. cout << dp[n].F - k * penalty << '\n';
  83. }
  84.  
  85. int32_t main() {
  86. Waimai;
  87. solve();
  88. }
Success #stdin #stdout 0.01s 5436KB
stdin
Standard input is empty
stdout
0