Description

LXX学习了N种算法知识，并且对于不同的算法知识掌握的程度不一样。为了能够在比赛中取得更好的成绩，他需要把自己的弱项填补。 就像木桶一样，能盛多少水，并不取决于桶壁上最高的那块木板，而恰恰取决于桶壁上最短的那块。已知LXX对第i种算法知识的能力值为Ai。LXX去向好心的上帝求救，上帝送给了他一个修补工具，但是最多只能使用M(M*L<N)次，且只能使连续的不超过L种知识的能力值提高至任意数值。现在问如何修补才能使能力值最小的最大呢？能力值的序列可以看成跟木桶类似的环状。

Input

第1行包含3个正整数，N, M, L。1≤N≤1000，1≤L≤20
第2行包含N个正整数，A1...Ai...An，1≤Ai≤1000000000

Output

每行输出结果。

Sample Input

8 2 3

8 1 9 2 3 4 7 5

Sample Output

7

Hint

我们要使最终能力值的最小值尽可能大，求这个最大的最小能力值。
这是一个环状木桶，最好的办法是，我们修补｛8,1,2｝和{4,5,6}这两组位置（即把他们的值提高到很大很大），还剩下两个数没被提升，第3个数9和第7个数7，最小值是7。

Source

2017年暑期集训校队选拔

Author

廖璇璇

#include <cstdio>

#include <time.h>

#include <cmath>

#include <stdlib.h>

#include <cstring>

using namespace std;

long long int a[];

long long  int n,m,l;

bool zs(long long  int y,long long int x)

{

    long long int mm=m;

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

    {

        if(a[y+i]<x)

        {

            mm--;

            i=i+l-;

        }

    }

    if(mm<)return false;

    return true;

}

bool jug(long long int x)

{

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

    {

        if(zs(i,x))

            return true;

    }

    return false;

}

int main()

{

    while(~scanf("%lld%lld%lld",&n,&m,&l))

    {

        long long int ma=,mi=,mid;

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

        {

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

            a[n+i]=a[i];

            if(ma<a[i])ma=a[i];

            if(mi>a[i])mi=a[i];

        }

        while(mi<=ma)

        {

            mid=(mi+ma)>>;

            if(jug(mid))

            {

                mi=mid+;

            }

            else

                ma=mid-;

        }

        //  printf("%d\n",mid);

        if(jug(mid))

        {

            while(jug(mid))

            {

                mid++;

            }

            printf("%lld\n",mid-);

        }

        else

        {

            while(!jug(mid))

            {

                mid--;

            }

            printf("%lld\n",mid);

        }

    }

    return ;

}