TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

38.9% (21/54)

Tags

Description

打敗了蘿莉後,那個長髮的女學生瞬間清醒了……原來她是個有強大法力的女學生叫作楓音,她也是在不知不覺中被控制了,因為她魔法很

強,所以敵人讓她在屋頂上監視著全校,同時還派了那蘿莉來控制她。

不過現在蘿莉被打敗了,還在喘息著,楓音也解除控制了!!!

於是妁艷和楓音決定要再進攻,一口氣把那蘿莉收服。因為那蘿莉不是學校的學生,是真的敵人,所以說不定能得到跟多消息!!!

楓音可以使出強大的魔法陣來攻擊敵人,不過這魔法陣很特別,它是一個由許多凹洞圍成的圓圈,而凹洞上面還要放魔法石,最後才能攻

擊。

每一個凹洞跟左右兩個洞都會有距離。也就是說,放了一些魔法石後,一個魔法石跟隔壁兩個魔法石也會有一些距離(可能會經過沒有魔法

石的凹洞,不過凹洞可以不算在距離內)。

而現在楓音要準備念咒語,所以給了妁艷一些魔法石,要妁艷把魔法石擺到一些洞上面,不過為了讓魔法更集中,希望能讓法石的”消失

度”越小越好。”消失度”要怎麼算呢?對於一個法石,把”它和左邊法石的距離”及”它和右邊法石的距離”加起來就是了。

希望在所有法石中,消失度最大的那個值能最小,法力會最好。

現在告訴你所有凹洞之間的距離,和法石的數量,請你讓最大消失度的值最小,並輸出那最大的消失度。

還有第一個洞跟第二個洞一定要擺魔法石!

Input Format

含多筆測資!

每一筆的第一行有兩個數字N ,M (4≤N,M≤30000)

N代表凹洞的數量(包括一定要擺的洞)

M代表魔法石的數量(包括一定要擺的魔法石)

再來一行會有N個數字(1≤數字≤30000)

第i個數字代表第i個洞跟第i+1個洞之間的距離,第N個數字則代表第N個洞跟第1個洞之間的距離

Output Format

每一筆測資皆要輸出一行

請讓最大的"消失度"最小

並輸出此"消失度"

Sample Input 1

6 4
2 3 2 3 2 3

Sample Output 1

8

Hints

2024/03/14 Update by FHVirus: 題目中沒有說明,不過「和左/右邊法石的距離」意思其實是「和左/右邊有放法石的洞的距離」,也可以理解成「一個洞只能放一個法石」。

Problem Source

原TIOJ1759 / problem setter: lnsuyn

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5