TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

90.9% (20/22)

Submission's AC Ratio

20.8% (36/173)

Description

傳說中在遙遠的ABCLS國有一隻喜歡疊烏龜的烏龜──草甘。
雖然他曾多次在疊烏龜時發生意外,但他對疊烏龜的熱愛卻絲毫不減。
有一天當草甘在疊烏龜時意外發現,前幾天撿回家的烏龜模型不是普通的模型,龜殼上的花紋隱藏了一些文字!
草甘決定將這些模型拿給烏龜王國有名的鑒定家──大明。

經過了八八六十四天的鑑定,大明發現了一件令人驚異的事情──這些模型上刻的是在烏龜王國近乎絕跡的古代咒術!
大明還在從小明手中搶來的書上發現這些咒術會使物質變得不穩定,
只要念出如「嗚啦啦啦嗚啦啦嗚啦阿拉拉阿嚕嚕啦啦嚕嗚呱呱嗚嗚啦」等咒語,再將兩個同時刻有咒術的物質靠近,他們就會合而為一。

聽到這些之後,草甘非常開心。既然這些烏龜模型可以融合,就代表說他能疊出更與眾不同的疊烏龜了!一如違和度超高的烏龜塔之類。

在草甘努力不懈的實驗下,他發現:

  1. 如果你把一堆烏龜模型融合起來,他們的違和度會相加。
  2. 念咒語時,模型會發出違和光芒,x個模型合出的模型會有強度x2的違和光芒。
  3. 一隻違和度c的烏龜如果放在烏龜塔的第m層,看起來會有c*(m-1)的違和度。
  4. 烏龜塔的違和度是所有烏龜看起來的違和度減掉所有違合光芒的強度。

現在草甘已經疊出了一個烏龜塔,他希望把某些連續的烏龜融合成一隻,以達成更高的違和度。
請問,草甘最多能疊出違和度多高的烏龜塔?對了,為了避免烏龜塔太矮,每個要融合的連續區段長度都不能包含超過k隻烏龜。

Input Format

第一行有兩個數字n, k。代表一共有n隻烏龜,連續區段最多可以包含k隻烏龜。
第二行有n個數字,分別代表烏龜塔中由下而上每隻烏龜的違和度。

Output Format

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

Sample Input

4 2
1 2 -3 -4

Sample Output

-15

Hints

對於 30%的測資 1 ≤ k ≤ n ≤ 500
對於 40%的測資 1 ≤ k ≤ 200 ≤ n ≤ 1,000
對於 70%的測資 1 ≤ k ≤ 500 ≤ n ≤ 200,000
對於100%的測資 1 ≤ k ≤ n ≤ 500,000
對於100%的測資輸出在 -1014 ~ 1014

以範測而言,若將1 2 -3 -4分為: [1] [2 -3] [-4] 會得到 (0 - 1) + ((-1)*1 - 4) + ((-4)*2 - 1) = -15


正當草甘開心的在欣賞超級違和的烏龜塔時,突然開始天搖地動。一片光芒亮得草甘
幾乎睜不開眼。而在那陣陣金光中,似乎有隻烏龜緩緩的步出……
--- to be continue.

Problem Source

原TIOJ1676 / 建國中學99年校內培訓contest #4 prob 5
problem setter:worm

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536
7 2000 65536 65536
8 2000 65536 65536
9 2000 65536 65536