TopCoder

User's AC Ratio

0.0% (0/1)

Submission's AC Ratio

0.0% (0/1)

Tags

Description

「合眾國日本」政府準備興建一條從長崎直接通往中華聯邦的海底鐵路,

這個大工程其實是可以分成N項花費時間都是1的基礎小工程來做的,

每一間公司只能做一件事情,看是要處理一項工程,

或者是將他負責的所有工程發包給兩家公司之後進行監督。

工程全部結束後監督公司必須負責檢查。

如果監督公司上面還有監督公司,那麼上面的監督公司還要在檢查一遍,依此類推。

一間公司在同一時間只能興建或檢查一樣工程,

但時同一時間可能有很多公司在進行建造或檢查工作。

給你這些工程的資料,你能夠算出最少要花費多少時間才能完成嗎?

Input Format

第一行有一個整數N代表有幾件工程,(N<=250)
接下來有N行,每行一個數字代表一項工程的檢查所需時間。

Output Format

請輸出最少要花費多少時間才能完成工作。

Sample Input 1

3
1
2
3

Sample Output 1

10

Sample Input 2

4
1
2
3
4

Sample Output 2

16

Hints

第一組測資有三個工程,監督所需時間分別是1、2、3。 最佳的分配方法如圖所示。 A公司將工程1、2分配給B公司,而工程3分給C公司。 B公司又分別將工程分給D公司跟E公司。 所以當D公司跟E公司花費1的時間做完後,B公司花3的時間檢查。 B檢查完後又由A檢查全部的三個工程,又花費6的時間。 所以一直到時間10全部的工作才做完。(10=6+3+1)自己看著辦吧 ;)

※2008/07/10 補上範例測資說明 by akira。

Problem Source

原TIOJ1362 / 快樂暑假營第一次練習比賽。Problem Setter:akira

Subtasks

No. Testdata Range 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

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
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10