51Nod 1711 平均数

#include<bits/stdc++.h>
using namespace std;

#define MEM(a,b,start,end) for(int ii=start;ii<=end;ii++) a[ii]=b
#define low(x) (x&(-x))
typedef long long LL;
typedef double D;
const int maxn=100000+100;
const double EPS=1e-6;

int tree[maxn];
D ans[maxn];
struct Node{
    
    D val;
    int id;
}node[maxn];
int n;
LL k;

inline bool cmp(Node a,Node b){
    
    return a.val<b.val;
}

inline void add(int ind,int val){
    
    while(ind<=n+1){
        
        tree[ind]+=val;
        ind+=low(ind);
    }
}

inline LL sum(int ind){
    
    LL s=0;
    while(ind){
        
        s+=tree[ind];
        ind-=low(ind);
    }
    return s;
}

bool kaven(double x){
    
    MEM(tree,0,1,n+1);
    LL cnt=0;
    for(int i=0;i<=n;i++) node[i].val=ans[i]-x*i,node[i].id=i+1;
    sort(node,node+1+n,cmp);
    for(int i=0;i<=n;i++){
        
        cnt+=sum(node[i].id);
        add(node[i].id,1);
    }
    if(cnt>=k) return true;
    return false;
}

int main(){
    
    scanf("%d%lld",&n,&k);
    ans[0]=0.0;
    for(int i=1;i<=n;i++) scanf("%lf",&ans[i]),ans[i]+=ans[i-1];
    D l=0,r=100000.0;
    while(r-l>=EPS){
        
        D mid=(l+r)/2.0;
        if(kaven(mid)) l=mid;
        else  r=mid;
    }
    printf("%.5f\n",(l+r)/2.0);
}