P12928 [POI 2022/2023 R2] 伐木工人 / Drwale

翻译来自于 [LibreOJ](https://loj.ac/p/5023)。

**题目译自 [XXX Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi30-2/dashboard/) [Drwale](https://szkopul.edu.pl/problemset/problem/fh8k3DcWsZB3OwD8rSLJw7SQ/statement/)** 两位伐木工 Bajtek 和 Bitek 以相同速度砍伐 $n$ 块木材，初始堆放在一起。第 $i$ 块木材需耗时 $a_i$ 分钟。每次某位伐木工完成当前木材后，从堆顶取下一块。若两人同时完成，Bajtek 优先取木材。 你的任务是计算在最不利排列下，伐木工完成所有砍伐的最晚时间。

第一行包含一个整数 $n$ $(1 \leq n \leq 10^6)$，表示木材数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示每块木材的砍伐时间。 设 $A = a_1 + a_2 + \ldots + a_n$ 为总砍伐时间，满足 $A \leq 5000000$。

输出一个整数，表示伐木工完成砍伐的最长可能时间。

**样例 1 解释** 若木材按顺序 $1, 2, 3$ 排列（耗时 $1, 2, 3$），可达结果 $4$。Bajtek 先取木材 $1$（耗时 $1$），Bitek 取木材 $2$（耗时 $2$）。$1$ 分钟后，Bajtek 取木材 $3$（耗时 $3$）。$4$ 分钟后，所有木材砍伐完成。 **附加样例** 1. $n=6, a_i = i$，答案为 $13$。 2. $n=1000, a_i = 1$，答案为 $500$。 3. $n=10, a_i = 2^{i-1}$，答案为 $767$。 4. $n=2, a_i = 2500000$，答案为 $2500000$。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 10$ | $5$ | | $2$ | $A \leq 500$ | $15$ | | $3$ | $A \leq 10000$ | $20$ | | $4$ | $A \leq 100000$ | $20$ | | $5$ | $A \leq 1000000$ | $20$ | | $6$ | 无附加限制 | $20$ |