TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

60.0% (6/10)

Tags

Description

學姐作為一名餐廳廚師,除了要做出好吃的料理,還要盡早完成菜單,讓客人不要等太久。今天餐廳突然同時來了 $N$ 名客人,每個人都會點一道菜,第 $i$ 個客人的餐點需要 $A_i$ 分鐘來完成,學姐一次只能做一道菜,而且開始做一道菜就一定要先把這道菜做完,她希望讓客人等待的時間總和越少越好,請告訴她怎麼最小化等待時間的總和。

Input Format

輸入有兩行,第一行包含一個正整數 $N$ 代表客人的數量。
第二行有 $N$ 個正整數,第 $i$ 個正整數 $A_i$ 代表完成第 $i$ 個客人的餐點所需的時間。

  • $1 \le N \le 10^ 5$
  • $1 \le A_i \le 10^ 5$

Output Format

輸出只有一行,包含一個正整數代表客人總等待時間的最小值。

Sample Input 1

3
1 2 3

Sample Output 1

10

Sample Input 2

4
1 1 1 100

Sample Output 2

109

Hints

Problem Source

AP325

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~13 無額外限制 100

Testdata and Limits

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