#2713. 修复假山

修复假山

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一座残破的石质假山,可以把它看作二维平面上用单位宽度的岩石堆叠而成的。经过风雨的侵蚀,它已经没有以往那么雄伟了,现在需要你的帮助来让它变得更高一些。

由于经费有限,最多只能提供给你n\red{n}块石块,希望你能够把它们堆到假山上之后得到的山峰最高(也就是二维平面上最高的一列的高度最高)。但是新堆叠上去的石块需要符合一定的稳定结构,每一块新增的石块只能放在一个已有岩石或者已填充的石块的正上方,并且该石块的左下方和右下方也必须都有一个岩石或者石块。能否请你计算得出能够修复出来的假山的高度最高可以是多少?

img

如上图所使,当残破的假山如左边所示,在最多提供n\red{n}个石块时,能够修复出来的最高的假山为右图。

输入格式

第一行输入两个正整数w,n\red{w,n}分别表示现存假山的宽度和最多提供的石块的个数;

接下来w\red{w}行,每行一个正整数hi\red{h_i}表示现存假山的每一列的高度。

输出格式

输出一个整数表示修复后的假山的最高高度

样例

输入样例

3 100
2
2
2

输出样例

3

提示

对于其中20%\red{20\%}的数据1<=w<=10,0<=n<=10,1<=hi<=10\red{1<=w<=10,0<=n<=10,1<=h_i<=10}

另有50%\red{50\%}的数据1<=w<=1000,0<=n<=109,1<=hi<=109\red{1<=w<=1000,0<=n<=10^9,1<=h_i<=10^9}

对于100%\red{100\%}的数据1<=w<=100000,0<=n<=1018,1<=hi<=109\red{1<=w<=100000,0<=n<=10^{18},1<=h_i<=10^9}

国庆集训7

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-10-3 14:40
结束于
2022-10-3 17:40
持续时间
3 小时
主持人
参赛人数
13