Problem Description

Consider a simple sequence which only contains positive integers as a1, a2 ... an, and a number k. Define ave(i,j) as the average value of the sub sequence ai ... aj, i<=j. Let’s calculate max(ave(i,j)), 1<=i<=j-k+1<=n.

 

Input

There multiple test cases in the input, each test case contains two lines. The first line has two integers, N and k (k<=N<=10^5). The second line has N integers, a1, a2 ... an. All numbers are ranged in [1, 2000].

 

Output

For every test case, output one single line contains a real number, which is mentioned in the description, accurate to 0.01.

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define SD(x) scanf("%lf",&x)

#define P_ printf(" ")

typedef long long LL;

const int MAXN=1e5+;

int sum[MAXN],s[MAXN],a[MAXN];

bool cross(int i,int j,int k){

    if((sum[j]-sum[i])*(k-i)>=(sum[k]-sum[i])*(j-i))return true;

    return false;

}

double flx(int i,int t){

    double temp;

    temp=1.0*(sum[t]-sum[i])/(t-i);

    return temp;

}

int main(){

    int N,k;

    while(~scanf("%d%d",&N,&k)){

        sum[]=;

        for(int i=;i<=N;i++)SI(a[i]),sum[i]=sum[i-]+a[i];

        int top=,low=;

        double ans=;

        for(int i=k;i<=N;i++){

            int j=i-k;

            while(top-low>=&&cross(s[top-],s[top],j))top--;

                s[++top]=j;

            while(top-low>=&&flx(s[low+],i)>=flx(s[low],i))low++;

            ans=max(ans,flx(s[low],i));

        }

        printf("%.2lf\n",ans);

    }

    return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int INF=0x3f3f3f3f;

#define mem(x,y) memset(x,y,sizeof(x))

#define SI(x) scanf("%d",&x)

#define PI(x) printf("%d",x)

#define SD(x) scanf("%lf",&x)

#define P_ printf(" ")

typedef long long LL;

const int MAXN=1e5+;

int sum[MAXN],s[MAXN],a[MAXN];

bool cross(int i,int j,int k){

    if((sum[j]-sum[i])*(k-i)>=(sum[k]-sum[i])*(j-i))return true;

    return false;

}

double flx(int i,int t){

    double temp;

    temp=1.0*(sum[t]-sum[i])/(t-i);

    return temp;

}

int erfen(int l,int r,int i){

    int mid;

    while(l<=r){

        mid=(l+r)>>;

        if(cross(s[mid],s[mid+],i))r=mid-;

        else l=mid+;

    }

    return r+;

}

int main(){

    int N,k;

    while(~scanf("%d%d",&N,&k)){

        sum[]=;

        for(int i=;i<=N;i++)SI(a[i]),sum[i]=sum[i-]+a[i];

        int top=,low=;

        double ans=;

        for(int i=k;i<=N;i++){

            int j=i-k;

            while(top-low>=&&cross(s[top-],s[top],j))top--;

                s[++top]=j;

            ans=max(ans,flx(s[erfen(,top,i)],i));

        }

        printf("%.2lf\n",ans);

    }

    return ;

}