### PROBLEM LINK:

**Author:** Abizer Lokhandwala

**Tester:** Hanlin Ren

**Editorialist:** Hanlin Ren

### DIFFICULTY:

SIMPLE

### PREREQUISITES:

Simple Math

### PROBLEM:

C cars are going through N tunnels. Each two consecutive tunnels are separated by a distance of D, and the speed of every car is S (the same). The i-th tunnel takes A[i] time to process a car, and if a new car enters a tunnel which is processing another car, it will wait until that car gets processed. If multiple cars enter, they line up as a queue. Initially, all N cars are in the queue of the first tunnel, and the first car is going to be processed. Suppose the first car exits tunnel N at time t_1 and the last car exits tunnel N at time t_2, compute t_2-t_1. The length of cars and tunnels are negligible.

### QUICK EXPLANATION:

The answer is

### EXPLANATION:

Letās prove that the answer is (\max_{i=1}^nA[i]) \cdot (C-1). Consider the following scenario where n=C=2:

- There are two cars, Reziba and Chef. Chef exits the first tunnel A[1] seconds later than Reziba.
- If A[1] < A[2], when Chef arrives the second tunnel, Rezibaās car is still being(or, waiting to be) processed. In this case, Chef and Reziba exit the second tunnel at a time difference A[2].
- If A[1] > A[2], when Chef arrives the second tunnel, Reziba has already left. In this case, the time difference is A[1].
- In conclusion, Chef exits the second tunnel \max(A[1],A[2]) seconds later than Reziba.

Let f[i][j] be the time that the i-th car exits from the j-th tunnel. Then f[2][k]-f[1][k]=\max(f[2][k-1]-f[1][k-1],A[k]). Thus f[2][n]-f[1][n]=\max_{i=1}^nA[i]. By the same reasoning, f[j][n]-f[j-1][n]=\max_{i=1}^nA[i] for all j>1. Thatās why the answer being simply

### ALTERNATIVE SOLUTION:

## a dp solution

Recall the definition of f[i][j] above. For the first car, f[1][j] is easy to compute:

For the i-th car, we have

since if the (i-1)-th car already exited the j-th tunnel, it doesnāt affect the i-th car, and the answer is f[i][j-1]+D/S+A[j]; otherwise the i-th car has to wait for him, and the answer is f[i-1][j]+A[j].

This solution has time complexity O(nC).

In fact, the exit time for C cars form an arithmetic progression, so we only need to compute f[1][\cdot] and f[2][\cdot], and the answer is

This is, in principle, correct. However it shouldnāt pass system test since we require an **absolute error** of 10^{-6} and the answer is around 10^{15}. This means our solution should have a **relative error** of 10^{-21}, which is not realistic even for 64-bit floating point numbers.

BTW, feel free to discuss about your approaches in comments!

### AUTHORāS AND TESTERāS SOLUTIONS:

Authorās solution can be found here.

Testerās solution can be found here.