题意：
某人要组织一场比赛。她有N道备选题，这场比赛有K题。每位选手要做这K题。她想，如果选手把这K题全做出来，选手会觉得这个比赛过于简单，很无趣。但如果选手只做出了很少的题目，又会觉得很难过。因此她想选这K道题，使得解出恰好K − 1题的概率尽量大。假设她已经进行了实验，得出了每道题被解出的概率。一共有不超过20组测试数据，对每组测试数据，1 ≤ K ≤ N ≤ 36。
卓亮的ppt还是不错的，题目比较好，然后ppt讲得也比gyz清楚。可惜这道题找不着那个网站，所以是自己人出的数据，而且卓亮化出来的式子虽然从公式上好理解，可惜直观上不好想，所以我yy了一个新公式。
首先数据范围很有特点（lmd如是说），折半搜索或许是可行的，但是如何统计呢？
如果裸做一种方案的键值是：f[k]=（1-a1）*a2*...*ak+a1*(1-a2)*a3*...*ak+...+a1*a2*a3*...*(1-ak),而这个式子是可拆的(分半提取公因式),
f[k]=【(1-a1)*a2*...*a[k/2])+(a1*(1-a2)*...)+...+(a1*...*(1-a[k/2])】*【a[k/2+1]*...an】+【a1*a2*...*a[k/2]】*【(1-a[k/2+1])*...*an+....】
第一个与第四个中括号的内容设为t，第二个与第三个设为s.
那么假设搜出前k/2的一种方案为t[i],s[i].现在搜后半搜出方案t[j],s[j]，统计答案即枚举每个i与j组合，即f=t[i]*s[j]+t[j]*s[i]=t[j]*s[i]-(-t[i])*s[j],就是叉积，即（tj，sj）X（-ti，si）
又变成在上凸壳中找最远点（还有一道http://blog.csdn.net/huyuncong/article/details/7258479）
#include <cstdio>
#include <cstdlib>
#include <cstring>
struct point{double x,y;}a[2000000];
point operator -(point p,point q){point u;u.x=p.x-q.x,u.y=p.y-q.y;return u;}
int n,m,k,v[100],ss;
double b[100],ans;
double cross(point p,point q) {return (p.x*q.y)-(p.y*q.x);}
double max(double x,double y) {return (x>y) ? x : y;}
struct hash
{
int l,lx,rx;
point d[100000];
int check(point e,point r,point u)
{
point p=r-e,q=u-e;
double pd=cross(p,q);
if (pd<=0) return 1;return 0;
}
void scan()
{
int i;
for (a[lx=++ss]=d[l],i=l-1;i>=1;i--)
{
for (;(ss>lx)&&(check(a[ss-1],a[ss],d[i]));ss--) ;
a[++ss]=d[i];
}
rx=ss;
}
}st[37];
void dfs(int x,int sum)
{
int l,i,j;
double s,t,tt;
if (sum>k) return ;
if (sum>n/2) return ;
if (x>n/2)
{
l=++st[sum].l,t=0,s=1;
for (i=1;i<=n/2;i++)
if (v[i]){
for (j=1,tt=1;j<=n/2;j++) if (v[j]){if (i!=j) tt*=b[j];else tt*=(1-b[j]);}
t+=tt,s=s*b[i];
}
if (k==sum) ans=max(ans,t);
st[sum].d[l].x=-t,st[sum].d[l].y=s;
return ;
}
v[x]=1,dfs(x+1,sum+1),v[x]=0,dfs(x+1,sum);
}
void search(double t,double s,int u)
{
int l=st[u].lx+1,r=st[u].rx,mid;
point p,q;
p.x=-t,p.y=-s;
for (;l<=r;)
{
mid=(l+r)>>1;
q=a[mid]-a[mid-1];
if (cross(p,q)<0) l=mid+1;else r=mid-1;
}
q=a[l],ans=max(ans,-cross(p,q));
q=a[l-1],ans=max(ans,-cross(p,q));
if (l<st[u].rx) q=a[l+1],ans=max(ans,-cross(p,q));
}
void dfs2(int x,int sum)
{
int i,j;
double t,s,tt;
if (sum>k) return ;
if (sum>n-n/2) return ;
if (x>n)
{
t=0,s=1;
for (i=n/2+1;i<=n;i++)
if (v[i]){
for (j=n/2+1,tt=1;j<=n;j++) if (v[j]){if (i!=j) tt*=b[j];else tt*=(1-b[j]);}
t+=tt,s=s*b[i];
}
if ((k==sum)||(0==sum)) ans=max(ans,t);
else {search(t,s,k-sum);}
return ;
}
v[x]=1,dfs2(x+1,sum+1),v[x]=0,dfs2(x+1,sum);
}
void qsort(int l,int r,hash &a)
{
int i=l,j=r;
double x=a.d[(l+r)>>1].x,y=a.d[(l+r)>>1].y;
point c;
for (;i<=j;)
{
for (;(a.d[i].y<y)||((a.d[i].y==y)&&(a.d[i].x<x));i++) ;
for (;(y<a.d[j].y)||((y==a.d[j].y)&&(x<a.d[j].x));j--) ;
if (i<=j)
c=a.d[i],a.d[i]=a.d[j],a.d[j]=c,
i++,j--;
}
if (i<r) qsort(i,r,a);
if (l<j) qsort(l,j,a);
}
void init()
{
int i;
scanf("%d%d\n",&n,&k);
for (i=1;i<=n;i++) scanf("%lf\n",&b[i]),b[i]/=100;
ans=0;
dfs(1,0);
for (i=1;i<=k;i++)
qsort(1,st[i].l,st[i]),st[i].scan();
dfs2(n/2+1,0);
printf("%.4lf\n",ans);
}
int main()
{
freopen("pro.in","r",stdin);
freopen("pro.out","w",stdout);
init();
return 0;
}