TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

86.7% (13/15)

Submission's AC Ratio

37.8% (28/74)

Tags

Description

最近胖胖國小又要舉辦園遊會了。

每年胖胖國小都會全校總動員,一起做一件有趣的事來做為園遊會的精神象徵與主題。

例如: 大胃王接力賽呀、環島接力馬拉松呀...,總之都會需要全校總動員才能夠達成。

今年胖胖國小則決定一起疊一個很大很大的羅漢,來做為這次活動的精神錦標。

現在全校的師生都已經站成一排了,為了平衡的關係,所以每個人頂多只被一個人踩。

不過為了防止跌倒,又為了防止最下面那層的人被壓死,所以可以扶著旁邊的欄杆。

因此對於某個人來說,除了受踩他的那個人的重量影響以外,不受更上層的人重量影響

為什麼會指受踩他的那個人影響呢?因為假如你被一個比你胖的人踩,你當然會覺得很不爽囉XD!

因此A踩B,則A體重一定小於B。

不過事情還沒解決,因為這個隊伍實在是太長了,所以要重新整頓非常困難。

因此每個人的右腳只可能踩位置在他右邊的人,左腳只能踩位置在他左邊的人。

當然踩人不一定要踩兩個,只踩一個也是OK的。

而且假如某個人兩隻腳踩的人疊的高度不一樣也沒關係,因為最後他們都可以在地上墊東西以達成平衡。

不過為了減少隊伍動到,所以有一個規定是說:

當A原本在B左邊,且B現在在A上方時,B原本右邊的人,A都不能踩

同樣的當A原本在B左邊,且A現在在B上方時,A原本左邊的人,B都不能踩

當然對於每一種採法都會有穩定與不穩定的事情發生。

因此穩定度的估算是: 所有踩與被踩的人的體重差的平方和

現在給你這n個人的體重(假設全部都不相同),問你說最穩定的穩定度為何?

Input Format

輸入一數n(1<=n<=2000000)。
接下來有n個整數,每個數皆不超過int儲存範圍。

Output Format

輸出一數代表最小穩定度的大小。

Sample Input

9
2 4 3 1 6 7 8 5 9

Sample Output

38

Hints

範例測資解釋:
總之堆積起來的圖會長這樣

因此最小穩定度是(2-1)2 + (3-2)2 + (4-3)2 + (5-1)2 + (6-5)2 + (7-6)2 + (8-7)2 + (9-5)2 = 38

※2009/7/23 補充題目敘述(by math120908): 感謝su_horng。

Problem Source

原TIOJ1549 / Problem Setter: math120908

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 6000 65536 262144
1 6000 65536 262144
2 6000 65536 262144
3 6000 65536 262144
4 6000 65536 262144