526互联

Present

发布时间 2023-06-15 14:26:23作者: o-Sakurajimamai-o
C. Present
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little beaver is a beginner programmer, so informatics is his favorite subject. Soon his informatics teacher is going to have a birthday and the beaver has decided to prepare a present for her. He planted n flowers in a row on his windowsill and started waiting for them to grow. However, after some time the beaver noticed that the flowers stopped growing. The beaver thinks it is bad manners to present little flowers. So he decided to come up with some solutions.

There are m days left to the birthday. The height of the i-th flower (assume that the flowers in the row are numbered from 1 to n from left to right) is equal to ai at the moment. At each of the remaining m days the beaver can take a special watering and water w contiguous flowers (he can do that only once at a day). At that each watered flower grows by one height unit on that day. The beaver wants the height of the smallest flower be as large as possible in the end. What maximum height of the smallest flower can he get?

Input

The first line contains space-separated integers n, m and w (1 ≤ w ≤ n ≤ 105; 1 ≤ m ≤ 105). The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a single integer — the maximum final height of the smallest flower.

Examples
input Copy
6 2 3
2 2 2 2 1 1
output Copy
2
input Copy
2 5 1
5 8
output Copy
9
Note

In the first sample beaver can water the last 3 flowers at the first day. On the next day he may not to water flowers at all. In the end he will get the following heights: [2, 2, 2, 3, 2, 2]. The smallest flower has height equal to 2. It's impossible to get height 3 in this test.

二分+差分

//求最大的最小值问题,首先就要想到二分,接着看题,又是加减连续的一段区间
//加减连续的区间就要想到用差分数组来维护
//对于一组花,设x是最大的最小高度,那么每次二分x,有:
//枚举每次mid,即check函数: 如果当前值小于最大的最小值,那就要浇花,一直浇到最大的最小值,并记录下天数
//如果天数够,那证明这个方案可行,然后我们的答案再向后推推,看看有没有更大的答案
//如果不够,那就是这个答案过于大了,那就向前推推.
//浇花时要利用差分数组来进行操作
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll res,a[N],c[N],l=2e9,r=-2e9,n,m,w;
bool check(int h)
{
    ll day=0,now=0;//day代表把花浇到指定高度需要的天数
    for(int i=1;i<=n;i++){
        now+=c[i];//当前高度;
        if(now<h){
            day+=h-now;
            c[i]+=h-now;
            if(i+w<=n) c[i+w]-=h-now;
            now+=h-now;
        }
    }
    return day<=m;
}
int main()
{
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l=min(l,a[i]);
        r=max(r,a[i]);
        c[i]=a[i]-a[i-1];//建立差分数组
    }
    r+=m+1;//因为要浇m天,右端点必须是最大的
    while(l<=r){
        ll mid=l+r>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
        for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1];//每次都要重置差分数组
    }
    cout<<res<<endl;
    return 0;
}