2163. Earliest Start, or Walk Out

Two tills work at different speeds. Till 0 takes s0 units of time per unit of work and till 1 takes s1, so a customer with d units of work occupies till j for d * sj units of time once started.

n customers arrive in non-decreasing order of arrival time. Customer i brings d[i] units of work and will wait at most p[i] units of time before giving up.

when customer i arrives: for each till j, start[j] = max(arrival[i], the moment till j is free) pick the till with the SMALLER start, and till 0 on a tie. this comparison looks only at the start times. It does NOT consider the speeds. if the chosen start is more than p[i] later than the arrival, the customer LEAVES. No till is touched and nothing else changes. otherwise the customer occupies that till from the chosen start until the chosen start plus d[i] * sj.

Print two integers: how many customers left, and the moment the last service ended, or 0 if nobody was served.

``` s0 = 1, s1 = 1, customers (0,5,0) (0,3,0) (0,4,0)

customer 0 has start 0 on both tills, the tie gives till 0, busy to 5. customer 1 has start 5 on till 0 and 0 on till 1, so till 1, busy to 3. customer 2 has start 5 and 3, so till 1, but 3 is 3 later than its arrival and its patience is 0, so it leaves. -> 1 5 ```

``` s0 = 1000, s1 = 1, customers (0,1000000,0) (0,1000000,0) (0,1000000,0)

customer 0 ties at start 0 and takes the SLOW till 0, busy to 10^9. customer 1 has start 10^9 on till 0 and 0 on till 1, so till 1, busy to 10^6. customer 2 has start 10^9 and 10^6, so the earliest is 10^6 on till 1, which is 10^6 later than its arrival. Its patience is 0, so it leaves. -> 1 1000000000 ```

## What most people try first

Choosing the till that will finish the customer soonest, which means comparing start[j] + d * sj rather than start[j]. That is the sensible rule and it is not the one written down. The second worked example exists to separate them: a customer who can start immediately on the slow till does so, and the fast till sits idle, which is exactly why one customer later walks out.

Modelling the speeds is the whole reason that distinction can be seen at all. With s0 = s1 the two rules agree on every input, so a problem without speeds would not be able to tell a correct solution from this particular wrong one.

## Why the patience test is where it is

Patience is compared against the WAIT, start - arrival, and not against the start or the departure. A customer who waits exactly p[i] stays, since the rule says "more than", so the comparison is start - arrival > p[i].

The test happens after the till is chosen and before anything is written. That ordering matters: a customer who leaves must leave no trace, so the chosen till's free time is unchanged and the next customer sees the shop exactly as it was. A solution that assigns first and un-assigns afterwards has to restore the free time exactly, and since the free time it overwrote is the one it needs back, that is a bug waiting to happen.

## Why one pass suffices

Arrivals are non-decreasing and a customer's fate depends only on the two free times at the moment they arrive. Those free times are determined entirely by the customers already processed, because a customer who left changed nothing and a customer who was served fixed one free time once and for all. So a single left to right pass holding two numbers is correct, and the declared outputs here are cross-checked against a version that rebuilds both free times from scratch at every arrival.

## Overflow

One service can be 10^6 units of work on a till of speed 1000, which is 10^9 units of time. With 2000 customers chaining on one till the free time can reach about 2 * 10^12, and arrivals add another 10^9. A signed 32 bit integer stops at 2147483647, so the free times, the starts and the answer all have to be 64 bit. The product d[i] * sj alone reaches 10^9, which still fits in 32 bits, so a build that is only careless about the product and not about the sums can pass the small tests and fail the long chains.

## Cost

O(n) time and O(1) memory beyond the input.

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ s0, s1 ≤ 1000` - `0 ≤ arrival ≤ 10^9`, non-decreasing over the input - `1 ≤ work ≤ 10^6` - `0 ≤ patience ≤ 10^9` - the till is chosen by the earlier start time, with ties going to till 0, and the speeds are not consulted - a customer leaves when the wait would be strictly more than their patience, and changes nothing