/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
Coshaman bought a roll cake of length L for the SCSC clubroom. The roll cake consists of L consecutive pieces of length 1, and the preference value of the i-th piece from the left is V_i.
Lulu wants to store the roll cake in a refrigerator. However, the clubroom refrigerator cannot store a roll cake of length greater than K, so Lulu decided to cut the roll cake into pieces of length at most K. Since cutting through a piece would make it ugly, Lulu must cut only between adjacent pieces.
When a roll cake is put into the refrigerator, only the end piece is visible from outside. Since the roll cakes must be put in with a fixed orientation, only the rightmost piece of each cut roll cake is visible. Lulu likes pretty things, so Lulu defines the beauty of storage as the sum of the preference values of the visible pieces.
Cutting a roll cake is hard work, so Lulu wants to store it with large beauty of storage while using little effort. When cutting a roll cake of length s into two roll cakes of lengths x and y (x+y=s), the required effort is x \times y. If several cuts are made, the effort required for the storage is the sum of the effort required for each cut.
Given L, K, and the preference values of each roll cake piece, find the maximum possible value of (\text{beauty of storage}) - (\text{effort required for storage}).
Constraints
- 1 \leq K \leq L \leq 1\,000\,000
- 0 \leq V_i \leq 10^9
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
L K V_1 V_2 \dots V_L
Output
Output the maximum possible value of (\text{beauty of storage}) - (\text{effort required for storage}).
Sample Input 1
4 4 1 2 3 4
Sample Output 1
4
Sample Input 2
3 1 1 2 3
Sample Output 2
3
表示言語
/ /Score : 100 points
문제
집돌이 페렐만은 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
表示言語
/ /配点 : 100 点
問題文
暁山 瑞希は SCSC の部室に長さ L のロールケーキを買ってきた．ロールケーキは長さ 1 の連続した L 個のピースからなり，左から i 番目のピースの好み度は V_i である．
ルルはロールケーキを冷蔵庫に保管しようとしている．しかし，部室の冷蔵庫には長さが K を超えるロールケーキを保管できないため，ルルはロールケーキを長さ K 以下に切り分けることにした．ロールケーキのピースを切ると見た目が悪くなるため，ピースとピースの間だけを切らなければならない．
ロールケーキを冷蔵庫に入れると，端のピースだけが外から見える．向きをそろえて入れる必要があるため，切り分けられた各ロールケーキの右端のピースだけが見える．かわいいものが好きなルルは，見えるピースの好み度の合計を保管の美しさと定義した．
ロールケーキを切るのは大変なので，保管の美しさを大きくしつつ，少ない労力で保管したい．長さ s のロールケーキを長さ x と y の 2 つのロールケーキに切るとき（x+y=s），消費される労力は x \times y である．複数回切る場合，保管に消費された労力は，各切断で消費された労力の総和である．
L，K，各ロールケーキのピースの好み度が与えられる．(\text{保管の美しさ}) - (\text{保管に消費された労力}) の最大値を求めよ．
制約
- 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{保管の美しさ}) - (\text{保管に消費された労力}) の最大値を出力せよ．
入力例 1
4 4 1 2 3 4
出力例 1
4
入力例 2
3 1 1 2 3
出力例 2
3