Going on Vacation
Katerina works a lot and urgently needs a vacation. She wants to take a trip to the islands and have as many consecutive days off as possible to relax, but she can only take one trip. Let the days be numbered from to . Katerina has some obligations in her schedule (the total number of them being ), which she has already committed to, corresponding to specific days: the -th obligation is scheduled for day .
Katerina is willing to cancel at most of her obligations in order to take more days off. Help her find out how many consecutive vacation days she can take.
Problem
Develop a program in one of the IOI languages (Pascal, C, C++, Java) which will read the data and find the maximum number of consecutive vacation days that Katerina can take.
Input Files:
The input file named maketime.in is a text file where the first line contains three integers , , and , separated in pairs by a single space: the total number of days, the number of obligations scheduled by Katerina, and the maximum number of obligations she is willing to cancel. The second line contains exactly integers (where and ): the days on which Katerina's obligations are scheduled.
Output Files:
The output file named maketime.out is a text file consisting of a single line containing an integer: the maximum number of days Katerina can take off for vacation.
Examples of input - output files:
1st
STDIN (maketime.in)
10 5 2
6 9 3 2 7
STDOUT (maketime.out)
5
Explanation: Katerina can cancel the obligations scheduled for days and . Thus, she can take a vacation from the st day to the th day, having a total of vacation days.
2nd
STDIN (maketime.in)
12 4 1
4 10 4 8
STDOUT (maketime.out)
5
Explanation: In the second example, Katerina can cancel her obligation for day and take a -day vacation (from the th day to the th day). Note that she has scheduled two obligations for the th day and is not willing to cancel both of them ().
3d
STDIN (maketime.in)
7 2 0
3 4
STDOUT (maketime.out)
3
In the third example, Katerina is not willing to cancel any obligation and can take a -day vacation, from the th day to the th day.
Constraints:
- For test cases worth 20%, of the total points, it will be:
1 Ν 100, 1 Μ 100, 0 Κ Μ - For test cases worth 50%, of the total points, it will be:
1 Ν 10.000, 1 Μ 20.000, 0 Κ Μ For test cases worth 100%, of the total points, it will be:
1 Ν 1.000.000, 1 Μ 2.000.000, 0 Κ ΜFormatting: In the output, each line terminates with a
newline
character.- Maximum execution time: 1 sec.
- Maximum available memory: 64 MB.
Comments