Rescue

The princess is trapped in a magic place. In this place, there are N magic stones. In order to rescue the princess, you should destroy all the stones.

The N stones are in a straight line. We number them as s1, s2, ... sn from left to right. Each stone has a magic strength m1, m2, ... mn. You have a powerful skill that can do some damage to the stones. To release the skill, you should stand to the right of some stone (si). Then you throw a power ball towards left. Initially, this ball has a power of p. When it hits a stone, it will do some damage to the stone and its power will be decreased, and the ball will continue to fly left to the next stone if its power is still positive. Formally, if you stand to the right of si and the power ball's initial power is p, then the ball will do Max(0, p - (i - j) * (i - j)) damage to sj, for each j <= i. So from this formula, we can see that the damage to stone sj is only determined by the initial power of the ball and the number of stones between si and sj.

A stone is destroyed if the accumulated damage you do is larger than its magic strength. Note that even if a stone is destroyed, it will not disappear; your magic ball will do damage to it and the power will be decreased by that stone. You are not strong enough so that you can release at most k magic balls. It will cost a lot of energy if the power of the magic ball is too high. So what is the minimum value of p with which you can destroy all the magic stones, with no more than k magic balls? You can choose where to release each magic ball as your will, and the power of the ball must be a positive integer.

Input

The first line is the number of cases T (T ≤ 100). For each case, the first line gives two integers n, k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 100000). The second line are n integers, giving m1, m2, ... mn (1 ≤ mi ≤ 109).

Output

Print minimum possible p in a line.

Sample Input

2
1 1
1
3 1
1 4 5
Sample Output

2

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
Mondo Rescue工具现在支持centos7.2或以上的系统版本吗?
-
ubantu 系统故障 想刷回windows 出现grub rescue
-
给移动硬盘安装rhel7提示grub rescue>
-
Rescue the Rabbit
-
FDNY to the Rescue!
-
CentOS7用Mondo Rescue备份却出现这个不知如何操作
-
路的距离的算法的问题,要求使用C程序谢谢
-
Brilliant Programmers Show的C语言解决方式
-
rails 2.3.4 使用 scaffold 生成代码问题
-
iframe高度自适应不对,scrollHeight取得的值不正确
-
寻找序列中的推断的数字,采用C程序的语言的程序设计的方式怎么做的
-
Save XX的代码编写过程,怎么实现
-
Brilliant Programmers Show
-
学会了这些技术,你离BAT大厂不远了
每一个程序员都有一个梦想,梦想着能够进入阿里、腾讯、字节跳动、百度等一线互联网公司,由于身边的环境等原因,不知道 BAT 等一线互联网公司使用哪些技术?或者该如何去学习这些技术?或者我该去哪些获取这些技术资料?没关系,平头哥一站式服务,上面统统不是问题。平头哥整理了 BAT 等一线大厂的必备技能,并且帮你准备了对应的资料。对于整理出来的技术,如果你掌握的不牢固,那就赶快巩固,如果你还没有涉及,现在...
程序员真是太太太太太有趣了!!!
网络上虽然已经有了很多关于程序员的话题,但大部分人对这个群体还是很陌生。我们在谈论程序员的时候,究竟该聊些什么呢?各位程序员大佬们,请让我听到你们的声音!不管你是前端开发...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学思路完全的清晰,可以试着关掉整合教程,摇两下头骨,哈一大口气,就在万事具备的时候,开整,这个时候你可能思路全无 ~中招了咩~ ,还有一些同学依旧在使用eclipse或者Myeclipse开发,我想对这些朋友说IDEA 的编译速度很快,人生苦短,来不及解释了,直接上手idea吧。这篇文章每一步搭建过程都测试过了,应该不会有什么差错。本文章还有个比较优秀的特点,就是idea的使用,基本上关于idea的操作都算是比较详细的,所以不用太担心不会撸idea!最后,本文
1行Python代码制作动态二维码
目录 1、普通二维码 2、艺术二维码 3、动态二维码 在GitHub上发现了一个比较有意思的项目,只需要一行Python代码就可以快捷方便生成普通二维码、艺术二维码(黑白/彩色)和动态GIF二维码。 GitHub网站参见:https://github.com/sylnsfar/qrcode 用法比较简单,直接通过pip安装即可。 pip3 install myqr 安装过程如下所...
知乎上 40 个有趣回复,很精辟很提神
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 |佚名来源 |网络整理,版权归原作者所有,侵删。1交朋友的标准是什么?- Ques...
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
用Python分析2000款避孕套,得出这些有趣的结论
到现在为止,我们的淘宝教程已经写到了第四篇,前三篇分别是: 第一篇:Python模拟登录淘宝,详细讲解如何使用requests库登录淘宝pc端。 第二篇:淘宝自动登录2.0,新增Cookies序列化,教大家如何将cookies保存起来。 第三篇:Python爬取淘宝商品避孕套,教大家如何爬取淘宝pc端商品信息。 今天,我们来看看淘宝系列的第四篇 我们在上一篇的时候已经将淘宝数据爬取下来了,...
程序员必备几款软件(实用、开源)
目录 Notepad++ tiny c compiler(tcc编译器) Notepad++ 软件介绍 程序员必备的文本编辑器,软件小巧高效,支持27种编程语言,兼容C,C++ ,Java ,C#, XML, HTML, PHP,JS 等, Notepad++ 可完美地取代微软的记事本。 下载链接http://www.188soft.com/soft/906144.html 软件特点 这是 Win...
一个即将走向社会的软件技术专业学生的感想
不知道为什么,总是喜欢在晚上学习,好像晚上学习也更有效率,而且晚上我也比较喜欢瞎想。一望无垠的夜空,独自一个人站在阳台上,望着深邃的星空,便总会陷入沉思,或思索未来的生活,或怀念过往的人生。 我为什么会选择软件技术专业 对于为什么会选择软件技术专业呢?原因其实很简单,亲戚朋友们都说做这个赚钱,身边也不乏做IT行业的人,所以,可以说我是为了钱,可能有人会说我比较势利吧,但是谁能说自己不喜欢钱呢?再加...
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
为什么我不建议你在当前购买 5G 手机
首发于公众号:BaronTalk,欢迎关注 每年的八九月份都是各大厂商发布年自己旗舰机的时候,最近 vivo、oppo、小米、华为、苹果接连发布了自己的年度旗舰,这当中除了苹果,其它厂商均发布了 5G 版本手机。恰逢国庆,势必会迎来一波换机潮,而各大厂商发布的 5G 手机很可能会成为很多同学的首选,今天我要来给准备购买 5G 手机的同学泼泼冷水。 先抛出观点:**对于普通消费者,当前不适合购...
win10电脑工具整理 - 常用工具!
如题,本文主要为博主对电脑上安装的一些软件,所做的整理,当做备份用吧。 一、分类 系统工具 办公软件 编程开发 数据库相关 图片视频工具 网络及下载工具 解压缩工具 影音娱乐工具 二、软件工具 1.系统工具 1.1. 磁盘管理 PartAssist:一款好用的磁盘分区管理工具。 1.2. 修复、引导 EasyBCD:一款常用的系统引导和修复工具。 1.3. 虚拟机管理工具 win10...
第二弹!python爬虫批量下载高清大图
文章目录前言下载免费高清大图下载带水印的精选图代码与总结 前言 在上一篇写文章没高质量配图?python爬虫绕过限制一键搜索下载图虫创意图片!中,我们在未登录的情况下实现了图虫创意无水印高清小图的批量下载。虽然小图能够在一些移动端可能展示的还行,但是放到pc端展示图片太小效果真的是很一般!建议阅读本文查看上一篇文章,在具体实现不做太多介绍,只讲个分析思路。 当然,本文可能技术要求不是特别高,但可以...
面试官,不要再问我三次握手和四次挥手
三次握手和四次挥手是各个公司常见的考点,也具有一定的水平区分度,也被一些面试官作为热身题。很多小伙伴说这个问题刚开始回答的挺好,但是后面越回答越冒冷汗,最后就歇菜了。 见过比较典型的面试场景是这样的: 面试官:请介绍下三次握手 求职者:第一次握手就是客户端给服务器端发送一个报文,第二次就是服务器收到报文之后,会应答一个报文给客户端,第三次握手就是客户端收到报文后再给服务器发送一个报文,三次握手就...
Java 爬虫遇到需要登录的网站,该怎么办?
这是 Java 网络爬虫系列博文的第二篇,在上一篇 Java 网络爬虫,就是这么的简单 中,我们简单的学习了一下如何利用 Java 进行网络爬虫。在这一篇中我们将简单的聊一聊在网络爬虫时,遇到需要登录的网站,我们该怎么办? 在做爬虫时,遇到需要登陆的问题也比较常见,比如写脚本抢票之类的,但凡需要个人信息的都需要登陆,对于这类问题主要有两种解决方式:一种方式是手动设置 cookie ,就是先在网站上...
div+css实现水平/垂直/水平垂直居中超详解
单个元素 水平居中 1.margin:0 auto方法 wrapper相对屏幕居中 &lt;div class="wrapper"&gt;&lt;/div&gt; body{ width: 100%; } .wrapper{ margin: 0 auto; width: 120px; height: 120px; background-color: purple; } ...
为什么程序员在学习编程的时候什么都记不住?
在程序员的职业生涯中,记住所有你接触过的代码是一件不可能的事情!那么我们该如何解决这一问题?作者 |Dylan Mestyanek译者 | 弯月,责编 | 屠敏出品 |...
500行代码,教你用python写个微信飞机大战
这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!让他们的左手 / 右手有节奏有韵律的朝着同一个方向来回移动起来! 这是史诗级的发明,是浓墨重彩的一笔,是…… 在一阵抽搐后,我结束了游戏,瞬时觉得一切都索然无味,正在我进入贤者模式时,突然想到,如果我可以让更多人已不同的方式体会到这种美轮美奂的感觉岂不美哉? 所以我打开电脑,创建了一个 `plan_game.py`……
唐僧团队要裁员,你会裁谁?
提问: 西游记取经团为了节约成本,唐太宗需要在这个团队里裁掉一名队员,该裁掉哪一位呢,为什么? 为了完成西天取经任务,组成取经团队,成员有唐僧、孙悟空、猪八戒、沙和尚、白龙马。 高层领导: 观音 项目经理: 唐僧 技术核心: 孙悟空 普通团员: 猪八戒、沙和尚 司机: 白龙马 这是个很有意思的项目团队 项目经理:唐僧 得道高僧。 唐僧作为项目经理,有很坚韧的品性和极高的原则性,不达目的不罢...
唏嘘!2019榜单出炉:铁打的Python连续3年第一,它居然跌出前十?
IEEE Spectrum2019年度编程语言排行榜最近刚刚出炉,Python不出意外的又拿了个第一,但是意料之外的是,曾经大火的PHP,居然跌出了前十!PHP曾被大家称...
2019诺贝尔经济学奖得主:贫穷的本质是什么?
2019年诺贝尔经济学奖,颁给了来自麻省理工学院的 阿巴希·巴纳吉(Abhijit Vinayak Banerjee)、艾丝特·杜芙若(Esther Duflo)夫妇和哈...
linux:最常见的linux命令(centOS 7.6)
最常见,最频繁使用的20个基础命令如下: 皮一下,这都是干货偶,大佬轻喷 一、linux关机命令: 1.shutdown命令安全地将系统关机(推荐)参数说明: [-r] 重启计算器。 [-h] 关机后关闭电源〔halt〕。 [-c] cancel current process取消目前正在执行的关机程序。 [-time] 设定关机〔shutdown〕前的时间。 shutdown -h now ...
只因写了一段爬虫,公司200多人被抓!
“一个程序员写了个爬虫程序,整个公司200多人被端了。” “不可能吧!” 刚从朋友听到这个消息的时候,我有点不太相信,做为一名程序员来讲,谁还没有写过几段爬虫呢?只因写爬虫程序就被端有点夸张了吧。 朋友说,消息很确认并且已经进入审判阶段了。 01.对消息进一步确认 朋友认识几个律师朋友,和他们有一些业务来往,得知他们想尝试把业务扩展到程序员这个群体。那段时间我刚好离职也有时间,在朋友...
别在学习框架了,那些让你起飞的计算机基础知识。
我之前里的文章,写的大部分都是与计算机基础知识相关的,这些基础知识,就像我们的内功,如果在未来想要走的更远,这些内功是必须要修炼的。框架千变万化,而这些通用的底层知识,却是几乎不变的,了解了这些知识,可以帮助我们更快着学习一门知识,更加懂得计算机的运行机制。当然,在面试中也经常会被问到,特别是对于应届生,对于春秋招,也可以看看我前阵子写过的文章历经两个月,我的秋招之路结束了!。也有读者经常问的计算...
100 美元一行代码,开源软件到底咋赚钱?
作者 | 顾钧责编 | 胡巍巍出品 | CSDN(ID:CSDNnews)很多创业公司苦恼于如何设计开源项目的商业模式,以下内容是笔者目前对此问题的摸索,权当抛砖引玉。开...
相关热词 c# mysql插入 c# sha256 加密 c#窗体上的叉添加事件 c#打印图片文件 c#後台調前台js c#控制台美化 c# 标记 浮点型 c#获取当前的农历日期 c# 构造函数重载 c# 页面功能注释