TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

87.9% (51/58)

Submission's AC Ratio

29.5% (92/312)

Tags

Description

修羅少年在魔獸帳號被砍掉之後的晚上做了一個夢:

修羅少年又夢到了自己登入了魔獸世界,他在艾爾文森林的林間小徑走著走著,在地上看到了一個閃閃發亮的物品,
正當他要拿起採礦錘去採礦的時候,他忽然發現其實那是一個錢包!打開之後裡面竟然有 5000G!這可以讓他在 8591 賺一筆了!

心情暢快不少的修羅少年又繼續在林間小徑走著,看到地上又出現了一個錢包!原來這是一條錢包的路。

是說這條傳說中的錢包的路是一條直線道路,修羅少年一登入時在道路的最左端(第一個錢包的位置),
每隔 100 碼的距離地上就會有一個錢包,每個錢包中有一定量的錢,然而這些錢包都是魔法錢包,
拿完錢後你不能把錢包拿走(不然錢包會把你吸進去),而要放在原地,當一個錢包的錢被拿走後,
由於魔法的力量會在固定的時間後恢復最初的金錢,經過修羅少年的實驗,對每個錢包,要花他不停頓地走 200 碼的時間才能復原。

雖然修羅少年不愛一百萬只愛台灣,不過他還是很好奇他可以在遊戲點數用完之前能夠拿到多少錢
(以修羅少年的腳程他不停頓地每走 100 碼的時間就要耗掉 1 點的遊戲點數,並且撿錢的時間極端可以忽略),
請你寫個程式幫他解決這個難題吧!

Input Format

第一行有兩個正整數 $N, K$($N, K \leq 10 ^ 6$),代表錢包的路有 $N$ 個錢包,且修羅少年的點數還有 $K$ 點。

第二行有 $N$ 個正整數 $a_i$($a_i \leq 10 ^ 6$),表示由左至右的錢包中有多少金幣。

Output Format

輸出一個整數,代表修羅少年最多可得到多少金幣。

Sample Input 1

5 4
3 4 3 5 1

Sample Output 1

18

Hints

修羅少年的走法:1-2-3-4-3,總共得到3+4+3+5+3=18的金幣

Problem Source

原TIOJ1636 / Problem Setter: DarkBtf
2021.02.15 Update: Added $\LaTeX$ by FHVirus

Subtasks

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

Testdata and Limits

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