fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll 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 = 2e5 + 5;
  13.  
  14. int N, K;
  15. ll pre[SIZE];
  16. double p1[SIZE], p2[SIZE];
  17.  
  18. tuple<double, double, int> st[SIZE];
  19. int L, R;
  20. pair<double, int> dp;
  21.  
  22. bool Del (tuple<double, double, int> t1, tuple<double, double, int> t2, double x) {
  23.     auto [m1, k1, c1] = t1;
  24.     auto [m2, k2, c2] = t2;
  25.     double v1 = m1 * x + k1, v2 = m2 * x + k2;
  26.     return v1 > v2 || (v1 == v2 && c1 >= c2);
  27. }
  28.  
  29. bool Del (tuple<double, double, int> t1, tuple<double, double, int> t2, tuple<double, double, int> t) {
  30.     auto [m1, k1, c1] = t1;
  31.     auto [m2, k2, c2] = t2;
  32.     auto [m, k, c] = t;
  33.     double x1 = (k2 - k1) / (m1 - m2), x2 = (k - k1) / (m1 - m);
  34.     return x1 > x2 || (x1 == x2 && c2 >= c);
  35. }
  36.  
  37. bool ok (double penalty) {
  38.     L = 1, R = 0;
  39.     st[++R] = {0, 0, 0};
  40.     dp = {0, 0};
  41.     FOR (i, 1, N) {
  42.         while (L + 1 <= R && Del (st[L], st[L + 1], p1[i])) L++;
  43.         auto [m, k, cnt] = st[L];
  44.         dp = {m * p1[i] + k + i + p2[i] + penalty, cnt + 1};
  45.         tuple<double, double, int> t = {-pre[i], dp.F - i - p2[i] + pre[i] * p1[i], dp.S};
  46.         while (L + 1 <= R && Del (st[R - 1], st[R], t)) R--;
  47.         st[++R] = t;
  48.     }
  49.     return dp.S <= K;
  50. }
  51.  
  52. void solve() {
  53.     cin >> N >> K;
  54.     FOR (i, 1, N) {
  55.         int t;
  56.         cin >> t;
  57.         pre[i] = pre[i - 1] + t;
  58.         p1[i] = p1[i - 1] + 1.00 / t;
  59.         p2[i] = p2[i - 1] + 1.00 * pre[i - 1] / t;
  60.     }
  61.     double l = 0, r = N + p2[N];
  62.     FOR (t, 1, 100) {
  63.         double mid = (l + r) / 2;
  64.         if (ok (mid)) r = mid;
  65.         else l = mid;
  66.     }
  67.     ok (r);
  68.     cout << fixed << setprecision (16) << dp.F - K * r << '\n';
  69. }
  70.  
  71. int main() {
  72.     Waimai;
  73.     solve();
  74. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000000000
https://ideone.com/GBMWrk
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!