DMOPC '22 Contest 4 P1 - Alone Time

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Alice and Bob are hanging out in a park near the university!

Unfortunately, since classes are happening, people keep walking through the park, disturbing the pair! There are N classes, and the i-th class ends at minute A_i, at which point students walk through the park. Thankfully, they only take 1 minute to leave the clearing.

Alice and Bob will stay in the park for M minutes, from minute 1 to minute M. Bob hates being disturbed, and so by bribing the university, he can make at most one class up to K minutes earlier or later (which will of course change when those students enter the park).

If he changes the time of at most one class optimally, what is the maximum contiguous section of time he and Alice can spend undisturbed?


1 \le N \le 10^6

N \le M \le 10^9

0 \le K \le 10^9

1 \le A_i \le M

A is sorted in strictly increasing order.

Subtask 1 [10%]

K = 0

Subtask 2 [20%]

N = 2

Subtask 3 [70%]

No additional constraints.

Input Specfication

The first line will contain three integers, N, M and K.

The next line will contain N integers, the array A.

Output Specification

Output the maximum time Bob and Alice can spend undisturbed if Bob moves the class optimally.

Sample Input 1

2 10 2
1 7

Sample Output 1


Explanation for Sample 1

By moving the second class back by two minutes, Alice and Bob can spend the time from minute 2 to minute 8 uninterrupted.

Sample Input 2

3 8 5
1 7 8

Sample Output 2


Explanation for Sample 2

One possible solution is for Bob to make the first class end at time 0 (before Alice and Bob arrive), and then Alice and Bob will have the time from minute 1 to minute 6 uninterrupted.


There are no comments at the moment.