763. A Speed That Meets Every Deadline
A machine must run n jobs in the order they are given. Job i has w[i] units of work
and a deadline d[i], counted in whole hours from the moment the machine starts.
The machine is booked by the hour: at speed s units per hour, job i occupies
ceil(w[i] / s) whole hours, and the next job starts only when that block ends. Job i is
therefore finished after
ceil(w[0] / s) + ceil(w[1] / s) + ... + ceil(w[i] / s)
hours, and that must not exceed d[i].
Print the smallest whole speed that meets EVERY deadline, or -1 if no speed does.
work 10 10 10, deadlines 2 4 6 -> 5
work 10 10 10, deadlines 1 2 3 -> 10
work 10 10 10, deadlines 1 1 3 -> -1
work 6 6 6, deadlines 3 6 9 -> 2
At speed 5 the three jobs take 2 hours each, finishing at hours 2, 4 and 6, exactly on time. At speed 4 the first job already takes 3 hours and misses its deadline of 2.
## How this differs from problem 751
Problem 751 has a single limit on the TOTAL. Here every prefix has its own limit, so a speed can
fail while the total still fits comfortably: 10 10 10 against deadlines 1 1 3 has a total
budget of 3 hours and three jobs that each need at least one hour, yet the second deadline is
unreachable whatever the speed. Checking only the last deadline accepts that input and prints a
speed, which is why the check has to test every job as it goes.
## Why the predicate is monotone
Raising s cannot raise any ceil(w / s), so every prefix total is non-increasing in s. If a
speed meets all the deadlines, so does every faster speed: each finish time is at or before where
it was. Feasible speeds therefore form a suffix and binary search finds the smallest.
Notice that this argument needs the deadlines to be independent of s, which they are. If a
deadline itself moved with the speed the shape could break, and the search would not be valid.
## The bounds
lo = 1. hi = max(w), because at that speed every job fits in one hour and no faster speed
changes anything: job i finishes at hour i + 1 counting from 1, and that is the earliest any
schedule can manage.
## When the answer is -1
Exactly when hi fails, that is when some job i has d[i] < i + 1 in 1-based counting. Test
hi once before searching and print -1 if it fails; there is no need for a separate rule.
## The boundary that breaks a careless implementation
The comparison goes AFTER adding the current job, not before. Testing total <= d[i] while
total still holds the previous job's finish time passes every input and is wrong on all of
them, and the tests 3 6 9 against 6 6 6 and 2 5 8 against the same work are there to
separate the two spellings.
The second is rounding: (w + s - 1) / s, never w / s + 1, which charges a phantom hour when
the division is exact.
## Overflow
At s = 1 the running total is sum(w), up to 10^5 * 10^9 = 10^14, and deadlines reach
10^14 too. Both need 64 bits. The check should abandon a candidate at the first missed
deadline, which keeps the total from ever running far past the largest deadline.
## Cost
Time O(n log(max w)). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ w[i] ≤ 10^9` - `1 ≤ d[i] ≤ 10^14`
Input
The first line contains a single integer n.
The second line contains n integers w[0] ... w[n-1], the work in each job, in the order they run.
The third line contains n integers d[0] ... d[n-1], the deadline of each job in hours.
Output
Print one integer, the smallest whole speed in units per hour that meets every deadline, or -1 if no speed does. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.