Grouped Carriages
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2100
Tags: binary search, data structures, dp, flows, greedy

Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.

A train contains $$$N$$$ carriages that are numbered from $$$1$$$ to $$$N$$$ from left to right. Carriage $$$i$$$ initially contains $$$A_i$$$ passengers. All carriages are connected by carriage doors, namely for each $$$i$$$ ($$$1\leq i\leq N-1$$$), carriage $$$i$$$ and carriage $$$i+1$$$ are connected by a two-way door.

Each passenger can move between carriages, but train regulation regulates that for each $$$i$$$, a passenger that starts from carriage $$$i$$$ cannot go through more than $$$D_i$$$ doors.

Define $$$Z$$$ as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of $$$Z$$$?

Input format:
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — the number of carriages.

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$) — the initial number of passengers in each carriage.

The third line contains $$$N$$$ integers $$$D_1, D_2, D_3, \ldots, D_N$$$ ($$$0 \leq D_i \leq N-1$$$) — the maximum limit of the number of doors for each starting carriage.

Output format:
An integer representing the minimum possible value of $$$Z$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
One strategy that is optimal is as follows:

- $$$5$$$ people in carriage $$$1$$$ move to carriage $$$4$$$ (going through $$$3$$$ doors).
- $$$3$$$ people in carriage $$$5$$$ move to carriage $$$3$$$ (going through $$$2$$$ doors).
- $$$2$$$ people in carriage $$$6$$$ move to carriage $$$5$$$ (going through $$$1$$$ door).
- $$$1$$$ person in carriage $$$6$$$ moves to carriage $$$7$$$ (going through $$$1$$$ door).

The number of passengers in each carriage becomes $$$[2,4,5,5,4,5,4]$$$.

Example input:
7
7 4 2 0 5 8 3
4 0 0 1 3 1 3

Example output:
5

Editorial:
Suppose we set the maximum number of passengers in the same carriage to be at most $$$Z$$$. If there is a valid strategy to fit the constraint, doing the same strategy for every maximum number of passengers in the same carriage that is greater than $$$Z$$$ is also possible. Hence, we can try to find the answer by doing binary search the answer.
Note that a passenger from carriage $$$i$$$ can move to carriage $$$j$$$ as long as $$$i-D_i \leq j \leq i+D_i$$$. So for each initial carriage $$$i$$$, create a segment $$$[i-D_i,i+D_i]$$$.
Suppose we try to find a valid strategy for moving the passengers with the constraint that the maximum number of passengers in the same carriage is at most $$$Z$$$. We can solve this greedily. Iterate the destination carriages from left to right to be filled with passengers. The initial carriages that can fill the current carriage are only the ones whose segments contain the current carriage.
Note that it is always optimal to take passengers from the segments with the smallest right endpoints first. We take the passengers until the current destination carriage reaches $$$Z$$$ passengers or there are no more segments to take from.
If there exists a non-empty segment of an initial carriage that cannot donate its passengers anywhere, then it is impossible.
We can do something like line sweep and prioritise the segments based on their right endpoints using priority queue or other data structures.
Time complexity: $$$O(N\log N\log\max(A))$$$