TopCoder

會寫程式的羊
咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩咩

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

75.0% (15/20)

Tags

Description

題本 PDF
傳說中在遙遠的ABCLS 國有一隻喜歡疊烏龜的烏龜――草甘。雖然他曾多次在疊烏龜時發生意外,但他對疊烏龜的熱愛卻絲毫不減。有一天當草甘在疊烏龜時意外發現,前幾天撿回家的烏龜模型不是普通的模型,龜殼上的花紋隱藏了一些文字!草甘決定將這些模型拿給烏龜王國有名的鑒定家――大明。
經過了八八六十四天的鑑定,大明發現了一件令人驚異的事情――這些模型上刻的是在烏龜王國近乎絕跡的古代咒術!大明還在從小明手中搶來的書上發現這些咒術會使物質變得不穩定,只要念出如「嗚啦啦啦嗚啦啦嗚啦阿拉拉阿嚕嚕啦啦嚕嗚呱呱嗚嗚啦」等咒語,再將兩個同時刻有咒術的物質靠近,他們就會合而為一。
聽到這些之後,草甘非常開心。既然這些烏龜模型可以融合,就代表說他
能疊出更與眾不同的疊烏龜了!一如違和度超高的烏龜塔之類。
在草甘努力不懈的實驗下,他發現:
1. 如果你把一堆烏龜模型融合起來,他們的違和度會相加。
2. 一隻違和度c的烏龜如果放在烏龜塔的第m層,看起來會有c×(m−1)的違和度。
3. 烏龜塔的違和度是所有烏龜看起來的違和度總和。
現在草甘已經疊出了一個烏龜塔,他希望把某些連續的烏龜融合成一隻,以達成更高的違和度。
請問,草甘最多能疊出違和度多高的烏龜塔?對了,為了避免烏龜塔太矮,每個要融合的連續區段長度都不能包含超過k隻烏龜

Input Format

每筆測資只包含兩行。第一行有兩個數字$n$,$k$。代表一共有$n$隻烏龜,連續區段最多可以包含$k$隻烏龜。第二行有$n$個數字,分別代表烏龜塔中由下而上每隻烏龜的違和度。
對於30%的測資$1\le k\le n\le 500$
對於40%的測資$1\le k\le 200\le n\le 1,000$
對於70%的測資$1\le k\le 500\le n\le 200,000$
對於100% 的測資$1\le k\le n\le 500,000$
對於100% 的測資輸出在 -1014 到 1014

Output Format

請輸出一個數字,代表融和某些烏龜後,最多可以疊出違和度多高的烏龜塔?

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

-7

Sample Input 2

4 2
-1 2 -3 4

Sample Output 2

8

Hints

Problem Source

NEOJ Problem 185

Subtasks

No. Testdata Range Constraints Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1
1 1000 131072 65536 2
2 1000 131072 65536 3
3 1000 131072 65536 4
4 1000 131072 65536 5
5 1000 131072 65536 6
6 1000 131072 65536 7
7 1000 131072 65536 8
8 1000 131072 65536 9
9 1000 131072 65536 10