1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 200010;
const double pi = acos(-1.);

struct Complex {
  double x, y;
  Complex() { x = y = 0; }
  Complex(double _x, double _y) { x = _x, y = _y; }
  friend Complex operator+(Complex x, Complex y) { return Complex(x.x + y.x, x.y + y.y); }
  friend Complex operator-(Complex x, Complex y) { return Complex(x.x - y.x, x.y - y.y); }
  friend Complex operator*(Complex x, Complex y) { return Complex(x.x * y.x - x.y * y.y, x.y * y.x + x.x * y.y); }
} a[maxn], b[maxn], c[maxn];

int n, k, rev[maxn];
double p[maxn], ans;

void dft(Complex *a, int lim, int ty) {
  int k = __builtin_ctz(lim);
  rep (i, 1, lim - 1) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1));
  rep (i, 1, lim - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
  for (int len = 1; len < lim; len <<= 1) {
    Complex rt = Complex(cos(pi / len), ty * sin(pi / len));
    for (int l = 0; l < lim; l += (len << 1)) {
      Complex wn = Complex(1, 0);
      for (int i = 0; i < len; i++, wn = wn * rt) {
        Complex x = a[l + i], y = a[l + i + len] * wn;
        a[l + i] = x + y, a[l + i + len] = x - y;
      }
    }
  }
}

void mul(Complex *a, int n, Complex *b, int m, Complex *c) {
  int lim = 1;
  while (lim <= n + m) lim <<= 1;
  rep (i, n + 1, lim - 1) a[i] = Complex();
  rep (i, m + 1, lim - 1) b[i] = Complex();
  dft(a, lim, 1), dft(b, lim, 1);
  rep (i, 0, lim - 1) c[i] = a[i] * b[i];
  dft(c, lim, -1);
  rep (i, 0, lim - 1) c[i].x /= lim;
}

vector<double> solve(int l, int r) {
  if (l == r) return vector<double>({1 - p[l], p[l]});
  int mid = (l + r) >> 1;
  auto ls = solve(l, mid), rs = solve(mid + 1, r);
  rep (i, 0, mid - l + 1) a[i] = Complex(ls[i], 0);
  rep (i, 0, r - mid) b[i] = Complex(rs[i], 0);
  mul(a, mid - l + 1, b, r - mid, c);
  vector<double> res;
  rep (i, 0, r - l + 1) res.emplace_back(c[i].x);
  return res;
}

double calc(int c) {
  auto f = solve(1, c);
  double s = 0;
  rep (i, (k + c + 1) >> 1, c) s += f[i];
  return s;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> k;
  rep (i, 1, n) cin >> p[i];
  sort(p + 1, p + n + 1), reverse(p + 1, p + n + 1);
  int l = (k + 1) >> 1, r = n >> 1;
  while (r - l > 1) {
    int m1 = (l + r) >> 1, m2 = m1 + 1;
    double v1 = calc(m1 << 1), v2 = calc(m2 << 1);
    if (v1 > v2) chkmx(ans, v1), r = m1 - 1;
    else chkmx(ans, v2), l = m2 + 1;
  }
  rep (i, l, r) chkmx(ans, calc(i << 1));
  l = k >> 1, r = (n - 1) >> 1;
  while (r - l > 1) {
    int m1 = (l + r) >> 1, m2 = m1 + 1;
    double v1 = calc(m1 << 1 | 1), v2 = calc(m2 << 1 | 1);
    if (v1 > v2) chkmx(ans, v1), r = m1 - 1;
    else chkmx(ans, v2), l = m2 + 1;
  }
  rep (i, l, r) chkmx(ans, calc(i << 1 | 1));
  cout << fixed << setprecision(10) << ans << '\n';
}