问题 I: 湾辟丝
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:22
解决:7
题目描述
草帽一行踏上了伟大航路的征程,为了补充物资以及强化万里阳光号,船长路飞决定搜集沿途的秘宝,船员娜美是一个贪财的海贼,她会收集她所见到的每一个秘宝,但是在见识过大场面之后,她会对价值低于她期望值秘宝不屑一顾,在伟大航路上有n个秘宝,分布于1…n的位置,对于位置i的秘宝价值为a[i],每收集一个秘宝a[i],娜美的期望值会提高为秘宝价值a[i],娜美从可以选择从任意的x处开始收集,但是一旦她开始收集,贪心的娜美会收集沿途所有价值高于期望值的秘宝,路飞想知道对于每一段长度为k的航路,娜美所能获得的最大价值总和是多少。
输入
第一行有2个数n k (1<=k<=n<=2e5)
第二行有n个数a1,a2…an (1<=ai<=1e9)
输出
输出一行n-k+1个数分别对应[a1…ak],[a2…ak+1]等航路所能获得的最大秘宝价值
样例输入 复制
6 5
5 1 6 3 4 5
样例输出 复制
11 12
提示
对于a2..a6的航路,若娜美从a2开始收集,仅能获得1+6=7的秘宝,而从a4开始收集,可以获得3+4+5=12的秘宝