← 返回题目列表

Codeforces · 1866/G

G. 分组车厢

中文机器翻译题面 查看原题

Pak Chanek 观察到,火车的车厢在早上出发时间和下午出发时间总是满员。因此,车厢之间需要保持平衡,这样只有几节车厢才不会太拥挤。

一列火车包含 $$$N$$$ 车厢,从左到右编号为 $$$1$$$ 到 $$$N$$$。 $$$i$$$ 车厢最初载有 $$$A_i$$$ 乘客。所有车厢均由车厢门连接,即对于每个 $$$i$$$ ($$$1\leq i\leq N-1$$$),车厢 $$$i$$$ 和车厢 $$$i+1$$$ 由双向门连接。

每个乘客都可以在车厢之间移动,但火车法规规定,对于每个 $$$i$$$,从车厢 $$$i$$$ 出发的乘客不能通过超过 $$$D_i$$$ 个门。

将 $$$Z$$$ 定义为移动后同一车厢内的乘客人数最多。 Pak Chanek 问,$$$Z$$$ 的最小可能值是多少?

输入

第一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — 车厢数量。

第二行包含 $$$N$$$ 整数 $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$) — 每节车厢的初始乘客数量。

第三行包含 $$$N$$$ 整数 $$$D_1, D_2, D_3, \ldots, D_N$$$ ($$$0 \leq D_i \leq N-1$$$) — 每个起始车厢的门数的最大限制。

输出

一个整数,表示 $$$Z$$$ 的最小可能值。

示例

输入 #1

7
7 4 2 0 5 8 3
4 0 0 1 3 1 3

输出 #1

5

注意

一种最佳策略如下:

- $$$5$$$车厢里的人$$$1$$$移动到车厢$$$4$$$(穿过$$$3$$$门)。
- $$$3$$$车厢里的人$$$5$$$移动到车厢$$$3$$$(穿过$$$2$$$门)。
- $$$2$$$车厢里的人$$$6$$$移动到车厢$$$5$$$(通过$$$1$$$门)。
- 车厢$$$6$$$中的$$$1$$$人移动到$$$7$$$车厢(通过$$$1$$$门)。

每节车厢的乘客人数变为$$$[2,4,5,5,4,5,4]$$$。