Description

著名出题人小Q的备忘录上共有n道可以出的题目，按照顺序依次编号为1到n，其中第i道题目的难度系数被小Q估计

为a_i，难度系数越高，题目越难，负数表示这道题目非常简单。小Q现在要出一套难题，他决定从备忘录中选取编

号连续的若干道题目，使得平均难度系数最高。当然，小Q不能做得太过分，一套题目必须至少包含k道题目，因此

他不能通过直接选取难度系数最高的那道题目来组成一套题。请写一个程序，帮助小Q挑选平均难度系数最高的题

目。

Input

第一行包含两个整数n,k(<=n<=,<=k<=n)，分别表示题目的总量和题数的下界。

第二行包含n个整数a_1,a_2,...,a_n(|a_i|<=^)，分别表示每道题目的难度系数。

Output

 输出一个既约分数p/q或-p/q，即平均难度系数的最大值。

Sample Input

  - -

Sample Output

/

HINT

Source

claris原创，本oj版权所有,翻版必究

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

db a[];

db s[];

db g[];

int mn[];

db eps = 1e-;

int n,k,ok = ;;ll y,x;

db l,r;

ll gcd(ll a,ll b)

{

    if(!b)

        return a;

    else

        return gcd(b,a % b);

}

int main()

{

    read(n);read(k);

    l=-,r=;

    duke(i,,n)

    {

        scanf("%lf",&a[i]);

        s[i] = s[i - ] + a[i];

    }

    duke(p,,)

    {

        ok = ;

        db mid = (l + r) / ;

        duke(i,,n)

        {

            g[i] = s[i] - (db)i * mid;

        }

        /*duke(i,1,n)

        cout<<g[i]<<" ";

        cout<<endl;*/

        duke(i,,n)

        {

            if(g[i] < g[mn[i - ]])

                mn[i] = i;

            else

                mn[i] = mn[i - ];

        }

        duke(i,k,n)

        {

            if(g[i] > g[mn[i - k]])

            {

                x = s[i] - s[mn[i - k]];

                y = i - mn[i - k];

                ok = ;

                break;

            }

        }

        if(ok == )

        {

            l = mid;

        }

        else

        {

            r = mid;

        }

    }

    ll g = gcd(x,y);

    if(g < )

    g = -g;

    if(g)

    x /= g,y /= g;

    printf("%lld/%lld\n",x,y);

    return ;

}

/*

5 3

1 4 -2 -3 6

*/

#include<cstdio>

#include<algorithm>

#include<cctype>

using namespace std;

typedef double db;

typedef long long ll;

const int N=1e5+;

int n,k,a[N],mn[N];

ll s[N],A,B,T;

db b[N];

inline int rd()

{

    char ch=getchar();

    int x=,f=;

    while(!isdigit(ch))

    {

        if(ch=='-') f=-;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        x=x*+(ch^);

        ch=getchar();

    }

    return x*f;

}

bool check(db mid)

{

    int i,j;

    b[]=a[]-mid;

    for(i=; i<=n; ++i)

    {

        b[i]=b[i-]+a[i]-mid;

        mn[i]= b[i] < b[mn[i-]]? i:mn[i-];

    }

    for(i = k; i<=n; ++i)

    {

        if(b[i]>b[mn[i-k]])

        {

            A = s[i] - s[mn[i-k]];

            B = i - mn[i-k];

            return true;

        }

    }

    return false;

}

inline ll gcd(ll x,ll y)

{

    return !y? x:gcd(y,x%y);

}

int main()

{

    int i,j;

    n=rd();

    k=rd();

    for(i=; i<=n; ++i)

    {

        a[i]=rd();

        s[i]=s[i-]+a[i];

    }

    db l=-1e8,r=1e8,mid;

    mn[]=;

    for(i=; i<=; ++i)

    {

        mid=(l+r)/;

        if(check(mid)) l=mid;

        else r=mid;

    }

    T=gcd(A,B);

    if(T<) T=-T;

    if(T) A/=T,B/=T;

    printf("%lld/%lld\n",A,B);

}