#P6984. [NEERC2015] Landscape Improved

[NEERC2015] Landscape Improved

题目描述

Louis LL Le Roi-Univers has ordered to improve the landscape that is seen from the royal palace. His Majesty prefers to see a high mountain.

The Chief Landscape Manager is going to raise a mountain for Louis. He represents a landscape as a flat picture on a grid of unit squares. Some of the squares are already filled with rock, while others are empty. This greatly simplifies the design. Unit squares are small enough, and the landscape seems to be smooth from the royal palace.

The Chief Landscape Manager has a plan of the landscape -- the heights of all rock-filled columns for each unit of width. He is going to add at most nn square units of stones atop of the existing landscape to make a mountain with as high peak as possible. Unfortunately, piles of stones are quite unstable. A unit square of stones may be placed only exactly on top of the other filled square of stones or rock, moreover the squares immediately to the bottom-left and to bottom-right of it should be already filled.

Existing landscape

Improved landscape

Your task is to help The Chief Landscape Manager to determine the maximum height of the highest mountain he can build.

输入格式

The first line of the input file contains two integers ww -- the width of the existing landscape and nn -- the maximum number of squares of stones to add (1w100000,0n1018).(1 \le w \le 100 000 , 0 \le n \le 10^{18}).

Each of the following ww lines contains a single integer hih_{i} -- the height of the existing landscape column (1hi109).(1 \le h_{i} \le 10^{9}).

输出格式

The output file shall contain the single integer -- the maximum possible landscape height after at most nn unit squares of stones are added in a stable way.

题目大意

给定序列 {hi}(i[1,w])\{h_i\}(i\in[1,w]) 和常数 nn

i(1,w)\forall i\in(1,w) ,仅当 hi1hih_{i-1} \geq h_ihi+1hih_{i+1} \geq h_i 时可使 hih_i 变为 hi+1h_i+1 ,且操作次数不能多于 nn 次。

求所有合法方案下,max{hi}\max\{h_i\} 的最大值。

$1\leq w\leq 10^5,1\leq h_i \leq 10^9,1\leq n\leq 10^{18}.$

8 4
3
4
2
1
3
3
2
4

5

3 100
3
3
3

4

提示

Time limit: 1 s, Memory limit: 256 MB.