← 返回题目列表

AtCoder · abc267_c

E. 索引×A(连续版)

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个整数序列 给出了 A=(A_1,A_2,\dots,A_N) 长度 N.

找到最大值 \displaystyle \sum_{i=1}^{M} i \times B_i 为连续子数组 B=(B_1,B_2,\dots,B_M) of A 长度 M.

注释

A 连续子数组 数列的 是通过去除 0 或更多初始条款以及 0 或原始数字序列中的更多最终项。

例如, (2, 3) 和 (1, 2, 3) 是连续的子数组 (1, 2, 3, 4),但是 (1, 3) 和 (3,2,1) 不是连续的子数组 (1, 2, 3, 4).

约束

  • 1 \le M \le N \le 2 \times 10^5
  • - 2 \times 10^5 \le A_i \le 2 \times 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

4 2
5 4 -1 8

示例输出 1

15

当 B=(A_3,A_4),我们有 \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15。 既然不可能实现 16 或更大的值,解决办法是 15.

请注意,您不能选择,例如, B=(A_1,A_4).


示例输入 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

示例输出 2

31