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