fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const int N = 423456;
  8. const ll inf = 1ll << 60;
  9.  
  10. struct info {
  11.   ll value;
  12.   int cnt;
  13.   int pre;
  14.  
  15.   info(ll value = 0, int cnt = 0, int pre = 0): value(value), cnt(cnt), pre(pre) {
  16.   }
  17. } dpl[N], dpr[N];
  18.  
  19. ll len, ans, a[N], f[2][N], sum[N];
  20. pair<int, int> ql[N], qr[N];
  21. int n, m, pos[N], pre[2][N];
  22. vector<int> pl, pr, pans;
  23.  
  24. ll get(int l, int r) {
  25.   int mid = l + r + 1 >> 1;
  26.   return (mid - l) * a[mid] - (sum[mid] - sum[l]) + (sum[r] - sum[mid]) - (r - mid) * a[mid];
  27. }
  28.  
  29. void solve(ll cost) {
  30.   int qlh = 1, qlt = 1;
  31.   int qrh = 1, qrt = 1;
  32.   ql[1] = qr[1] = make_pair(1, 0);
  33.   auto go = [&](info* dp, int from, int to, int diff) {
  34.     return make_pair(dp[from].value + get(from, to) + cost, dp[from].cnt + diff);
  35.   };
  36.   auto trans = [&](info* dp, pair<int, int>* q, int &h, int &t, int i, int c) {
  37.     pair<ll, int> w = go(dp, q[h].second, i, c);
  38.     dp[i] = info(w.first, w.second, q[h].second);
  39.     if (i == n) {
  40.       return;
  41.     }
  42.     ++q[h].first;
  43.     if (h < t && q[h].first == q[h + 1].first) {
  44.       ++h;
  45.     }
  46.     while (h <= t && go(dp, i, q[t].first, c) <= go(dp, q[t].second, q[t].first, c)) {
  47.       --t;
  48.     }
  49.     if (h > t) {
  50.       q[++t] = make_pair(i + 1, i);
  51.     } else {
  52.       if (go(dp, i, n, c) <= go(dp, q[t].second, n, c)) {
  53.         int low = q[t].first, high = n;
  54.         while (low < high) {
  55.           int mid = low + high >> 1;
  56.           if (go(dp, i, mid, c) <= go(dp, q[t].second, mid, c)) {
  57.             high = mid;
  58.           } else {
  59.             low = mid + 1;
  60.           }
  61.         }
  62.         q[++t] = make_pair(high, i);
  63.       }
  64.     }
  65.   };
  66.   for (int i = 1; i <= n; ++i) {
  67.     trans(dpl, ql, qlh, qlt, i, 1);
  68.     trans(dpr, qr, qrh, qrt, i, -1);
  69.   }
  70. }
  71.  
  72. ll solve() {
  73.   ll l = 0, r = inf;
  74.   while (true) {
  75.     ll mid = l + r >> 1;
  76.     solve(mid);
  77.     if (dpl[n].cnt <= m && -dpr[n].cnt >= m) {
  78.       vector<int> posl(dpl[n].cnt + 1);
  79.       for (int i = n, j = dpl[i].cnt; ~j; i = dpl[i].pre, --j) {
  80.         posl[j] = i;
  81.       }
  82.       vector<int> posr(-dpr[n].cnt + 1);
  83.       for (int i = n, j = -dpr[i].cnt; ~j; i = dpr[i].pre, --j) {
  84.         posr[j] = i;
  85.       }
  86.       for (int i = 0, j = -dpr[n].cnt - m; i < dpl[n].cnt; ++i, ++j) {
  87.         pos[i] = posl[i];
  88.         if (posl[i] <= posr[j] && posl[i + 1] >= posr[j + 1]) {
  89.           while (i + 1 <= m) {
  90.             pos[++i] = posr[++j];
  91.           }
  92.           return dpl[n].value - mid * m;
  93.         }
  94.       }
  95.     } else if (dpl[n].cnt > m) {
  96.       l = mid + 1;
  97.     } else {
  98.       r = mid - 1;
  99.     }
  100.   }
  101. }
  102.  
  103. void work(int cur, int l, int r, int ql, int qr) {
  104.   if (l > r) {
  105.     return;
  106.   }
  107.   int mid = l + r >> 1;
  108.   f[cur][mid] = inf;
  109.   for (int i = ql; i <= qr; ++i) {
  110.     if (f[cur][mid] > f[!cur][i] + get(i, mid)) {
  111.       f[cur][mid] = f[!cur][i] + get(i, mid);
  112.       pre[cur][mid] = i;
  113.     }
  114.   }
  115.   work(cur, l, mid - 1, ql, pre[cur][mid]);
  116.   work(cur, mid + 1, r, pre[cur][mid], qr);
  117. }
  118.  
  119. ll dp(int s) {
  120.   f[0][s] = 0;
  121.   int gl = s, gr = s;
  122.   for (int i = 1; i <= m; ++i) {
  123.     work(i & 1, pl[i], pr[i], gl, gr);
  124.     gl = pl[i];
  125.     gr = pr[i];
  126.   }
  127.   for (int i = m, j = s + n; ~i; j = pre[i & 1][j], --i) {
  128.     pos[i] = j;
  129.   }
  130.   return f[m & 1][s + n];
  131. }
  132.  
  133. void divide(int l, int r) {
  134.   if (l > r) {
  135.     return;
  136.   }
  137.   vector<int> fl = pl, fr = pr;
  138.   int mid = l + r >> 1;
  139.   ll w = dp(mid);
  140.   if (w < ans) {
  141.     ans = w;
  142.     pans = vector<int>(pos, pos + m + 1);
  143.   }
  144.   vector<int> fd = vector<int>(pos, pos + m + 1);
  145.   pl = fl;
  146.   pr = fd;
  147.   divide(l, mid - 1);
  148.   pl = fd;
  149.   pr = fr;
  150.   divide(mid + 1, r);
  151.   pl = fl;
  152.   pr = fr;
  153. }
  154.  
  155. int main() {
  156. #ifdef wxh010910
  157.   freopen("input.txt", "r", stdin);
  158. #endif
  159.   scanf("%d %d %lld", &n, &m, &len);
  160.   for (int i = 1; i <= n; ++i) {
  161.     scanf("%lld", &a[i]);
  162.     a[i + n] = a[i] + len;
  163.   }
  164.   for (int i = 1; i <= n * 2; ++i) {
  165.     sum[i] = sum[i - 1] + a[i];
  166.   }
  167.   ans = solve();
  168.   int p = 1;
  169.   for (int i = 1; i <= m; ++i) {
  170.     if (pos[i] - pos[i - 1] < pos[p] - pos[p - 1]) {
  171.       p = i;
  172.     }
  173.   }
  174.   for (int i = p; i <= m; ++i) {
  175.     pl.push_back(pos[i - 1]);
  176.     pr.push_back(pos[i]);
  177.   }
  178.   for (int i = 1; i <= p; ++i) {
  179.     pl.push_back(pos[i - 1] + n);
  180.     pr.push_back(pos[i] + n);
  181.   }
  182.   pans = vector<int>(pos, pos + m + 1);
  183.   divide(pl[0], pr[0]);
  184.   printf("%lld\n", ans);
  185.   vector<ll> res(m);
  186.   for (int i = 0; i < m; ++i) {
  187.     res[i] = (a[pans[i] + pans[i + 1] + 1 >> 1]) % len;
  188.   }
  189.   sort(res.begin(), res.end());
  190.   for (int i = 0; i < m; ++i) {
  191.     printf("%lld%c", res[i], i == m - 1 ? '\n' : ' ');
  192.   }
  193.   return 0;
  194. }
  195.  
Time limit exceeded #stdin #stdout 5s 53288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mE7QKW
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!