fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/M7thyT
language:
C++14 (gcc 8.3)
created:
1 year 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!