← All solutions

Shortest judge solution: 765 bytes. Shortest team solution (during contest): 815 bytes.

This problem is somewhat intimidating due to the long problem statement. However, once you get through the problem statement, it is actually pretty easy. Each ship determines an interval of time when the ferry cannot enter the lane, which translates to a time interval where the ship cannot start the crossing. You do have to take care to calculate everything correctly.

Fortunately, the answer is continuous, so we don’t have to worry about precision that much, and just use doubles.

Once we know all the forbidden intervals, the easiest way to determine the longest allowed interval is to sort all the forbidden interval beginnings and endings, going through them one by one, and keeping track of how many forbidden intervals are now open.