傳說中在遙遠的 ABCLS 國有一隻喜歡疊烏龜的烏龜──草甘。
雖然他曾多次在疊烏龜時發生意外,但他對疊烏龜的熱愛卻絲毫不減。
有一天當草甘在疊烏龜時意外發現,前幾天撿回家的烏龜模型不是普通的模型,龜殼上的花紋隱藏了一些文字!
草甘決定將這些模型拿給烏龜王國有名的鑒定家──大明。
經過了八八六十四天的鑑定,大明發現了一件令人驚異的事情──這些模型上刻的是在烏龜王國近乎絕跡的古代咒術!
大明還在從小明手中搶來的書上發現這些咒術會使物質變得不穩定,
只要念出如「嗚啦啦啦嗚啦啦嗚啦阿拉拉阿嚕嚕啦啦嚕嗚呱呱嗚嗚啦」等咒語,再將兩個同時刻有咒術的物質靠近,他們就會合而為一。
聽到這些之後,草甘非常開心。既然這些烏龜模型可以融合,就代表說他能疊出更與眾不同的疊烏龜了!一如違和度超高的烏龜塔之類。
在草甘努力不懈的實驗下,他發現:
現在草甘已經疊出了一個烏龜塔,他希望把某些連續的烏龜融合成一隻,以達成更高的違和度。
請問,草甘最多能疊出違和度多高的烏龜塔?對了,為了避免烏龜塔太矮,每個要融合的連續區段長度都不能包含超過 $k$ 隻烏龜。
第一行有兩個數字 $n, k$,代表一共有 $n$ 隻烏龜,連續區段最多可以包含 $k$ 隻烏龜。
第二行有 $n$ 個數字,分別代表烏龜塔中由下而上每隻烏龜的違和度。
請輸出一個數字,代表融和某些烏龜後,最多可以疊出違和度多高的烏龜塔?
對於 30%的測資 $1 \le k \le n \le 500$
對於 40%的測資 $1 \le k \le 200 \le n \le 1000$
對於 70%的測資 $1 \le k \le 500 \le n \le 200000$
對於100%的測資 $1 \le k \le n \le 500000$
對於100%的測資輸出在 $[-10 ^ {14}, 10 ^ {14}]$ 內
以範測而言,若將 1 2 -3 -4
分為:[1] [2 -3] [-4]
會得到 $(0 - 1) + ((-1) \times 1 - 4) + ((-4) \times 2 - 1) = -15$
正當草甘開心的在欣賞超級違和的烏龜塔時,突然開始天搖地動。一片光芒亮得草甘
幾乎睜不開眼。而在那陣陣金光中,似乎有隻烏龜緩緩的步出……
--- to be continue.
原TIOJ1676 / 建國中學99年校內培訓contest #4 prob 5
problem setter:worm
2021.03.13 Update: Added $\LaTeX$ by FHVirus
No. | Testdata Range | 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 |