a354. TOI 2021/04 潛力組：枯枝

題目描述

一棵造景樹可視為二元樹：每個節點最多有兩個子節點，並有一個非負的枯枝值。

空子樹的枯枝程度為 0。非空子樹的枯枝程度，等於其根節點的枯枝值，加上左、右子樹枯枝程度的較大者。整棵樹的枯枝程度就是根節點所代表子樹的枯枝程度。

園丁只留下各節點枯枝值的前序走訪序列，也就是依根節點、左子樹、右子樹的順序記錄。相同序列可能對應不同形狀的二元樹。請在所有具有此序列的二元樹中，求整棵樹枯枝程度的最小可能值與最大可能值。

輸入格式

第一行為整數 N，表示節點數。第二行有 N 個非負整數 dᵢ，依序表示前序走訪記錄的枯枝值。

• 1 ≤ N ≤ 1000
• 0 ≤ dᵢ ≤ 10⁹

原題分組：10 分資料 N ≤ 8；20 分資料 N ≤ 16；其餘 70 分無額外限制。

輸出格式

輸出兩個整數，依序為可能的最小枯枝程度與最大枯枝程度，以空白分隔。

來源

TOI 2021 年 4 月潛力組〈枯枝〉。依官方原題重新撰寫。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202104/Branch.pdf