fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, k;
  5.  
  6. double wcz;
  7.  
  8. long double sum[200007];
  9. long double rev[200007];
  10. long double pre[200007];
  11.  
  12. long double inf;
  13.  
  14. long double dpo[200007];
  15. long double dpn[200007];
  16.  
  17. long double x[200007];
  18. long double y[200007];
  19.  
  20. int l;
  21. vector <int> sta;
  22.  
  23. inline long double vec(int s, int a, int b)
  24. {
  25.     return (x[a]-x[s])*(y[b]-y[s])-(x[b]-x[s])*(y[a]-y[s]);
  26. }
  27.  
  28. int main()
  29. {
  30.     inf=1000000000.0;
  31.     inf*=inf;
  32.     scanf("%d%d", &n, &k);
  33.     for (int i=1; i<=n; i++)
  34.     {
  35.         scanf("%lf", &wcz);
  36.         sum[i]=wcz;
  37.         pre[i]=pre[i-1]+sum[i-1]/sum[i]+1.0;
  38.         rev[i]=1.0/sum[i]+rev[i-1];
  39.         sum[i]+=sum[i-1];
  40.     }
  41.     for (int i=1; i<=n; i++)
  42.     {
  43.         dpn[i]=pre[i];
  44.     }
  45.     for (int h=2; h<=k; h++)
  46.     {
  47.         for (int i=0; i<=n; i++)
  48.         {
  49.             dpo[i]=dpn[i];
  50.             dpn[i]=pre[i];
  51.  
  52.             x[i]=dpo[i]+rev[i]*sum[i]-pre[i];
  53.             y[i]=sum[i];
  54.         }
  55.         sta.clear();
  56.         l=0;
  57.         for (int i=1; i<=n; i++)
  58.         {
  59.             while(sta.size()>1 && vec(sta[sta.size()-2], sta[sta.size()-1], i-1)>=0)
  60.             sta.pop_back();
  61.             l=min(l, (int)sta.size()-1);
  62.             l=max(l, 0);
  63.             sta.push_back(i-1);
  64.             while(l+1<sta.size() && 1*x[sta[l+1]]-rev[i]*y[sta[l+1]]<=1*x[sta[l]]-rev[i]*y[sta[l]])
  65.             l++;
  66.             dpn[i]+=1*x[sta[l]]-rev[i]*y[sta[l]];
  67.         }
  68.     }
  69.     printf("%.10lf\n", (double)dpn[n]);
  70.     return 0;
  71. }
Success #stdin #stdout 0s 19824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000
https://ideone.com/xQ4qtd
language:
C++14 (gcc 8.3)
created:
8 years 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!