← 返回题目列表

AtCoder · scpc2026_div1_k

K. 存放蛋糕卷

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

表示言語

/ /

分数: 100 点

问题陈述

Coshaman 买了一个长度的蛋糕卷 L SCSC 俱乐部室。蛋糕卷由以下部分组成 L 连续片长度 1,以及的偏好值 i从左边算起第一个是 V_i.

露露想把蛋糕卷存放在冰箱里。然而,俱乐部冰箱不能存放长度大于 K,所以Lulu决定把蛋糕卷切成最多长度的块 K。由于切开一块会使它变得难看,露露必须只在相邻的块之间进行切割。

将蛋糕卷放入冰箱时,从外面只能看到末端部件。由于蛋糕卷必须以固定方向放入,因此只能看到切好的蛋糕卷最右边的一块。 Lulu喜欢漂亮的东西,所以Lulu将收纳之美定义为可见物品的偏好值之和。

切蛋糕卷是一项艰苦的工作,所以露露想用很少的力气将它存储起来具有很大的存储美感。切割一定长度的蛋糕卷时 s 分成两个长度的蛋糕卷 x 和 y (x+y=s),所需的努力是 x \times y。如果进行多次切割,则存储所需的努力是每次切割所需的努力的总和。

鉴于 L, K,以及每个蛋糕卷的偏好值,找到最大可能值 (\text{beauty of storage}) - (\text{effort required for storage}).

约束

  • 1 \leq K \leq L \leq 1\,000\,000
  • 0 \leq V_i \leq 10^9
  • 所有给定的数字都是整数。

输入

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

L K
V_1 V_2 \dots V_L

输出

输出最大可能值 (\text{beauty of storage}) - (\text{effort required for storage}).


示例输入 1

4 4
1 2 3 4

示例输出 1

4

示例输入 2

3 1
1 2 3

示例输出 2

3

表示言語

/ /

分数: 100 点

문제

SCSC SCSC L인 롤케이크를 사 왔다. 롤케이크는 길이가 1인 연속된 L개의 조각으로 이루어져 있으며, 왼쪽에서부터 i번째 조각의 선호도는 V_i이다.

루루는 롤케이크를 냉장고에 보관하려고 한다. 하지만 동아리방 냉장고는 길이가 K를 초과하는 롤케이크를 보관할 수 없기 때문에 루루는 롤케이크를 K 이하의 길이로 나누기로 했다. 롤케이크의 조각을 나누면 못생겨지기 때문에 조각과 조각 사이를 잘라야 한다.

롤케이크를 냉장고에 넣으면 맨 끝에 있는 조각만 밖에서 보이게 된다. 방향을 맞춰 넣어야 하기 때문에 잘린 각 롤케이크의 오른쪽 끝 조각만 눈에 보인다. 예쁜 것을 좋아하는 루루는 눈에 보이는 조각들의 선호도 합을 보관의 아름다움이라고 정의했다.

롤케이크를 자르는 것은 힘든 일이기 때문에 보관의 아름다움을 크게 하면서도 힘이 적게 들게 보관하고 싶다. 길이가 s인 롤케이크를 길이가 x와 y인 두 롤케이크로 자를 때 (x+y=s) 소모되는 힘은 xy이다. 여러 번 자르는 경우, 보관에 소모된 힘은 각 절단에서 소모되는 힘의 합이다.

L, K, 각 롤케이크 조각의 선호도가 주어질 때 (\text{보관의 아름다움}) - (\text{보관에 소모된 힘})의 최댓값을 구해 보자.

제한

  • 1 \leq K \leq L \leq 10^6
  • 0 \leq V_i \leq 10^9
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

L K
V_1 V_2 \dots V_L

출력

롤케이크를 보관할 때 (\text{보관의 아름다움}) - (\text{보관에 소모된 힘})의 최댓값을 출력한다.


입력 예 1

4 4
1 2 3 4

출력 예 1

4

입력 예 2

3 1
1 2 3

출력 예 2

3