/
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score: 100 points
Problem Statement
In EGOI Airport, there are N runways, numbered from 1 to N. In this airport, for an airplane, it takes K minutes to take off, and L minutes to land. During a takeoff or landing of an airplane, a runway is occupied by the airplane for a duration of K or L minutes.
JOI-kun is working at EGOI Airport. His job is to arrange the schedule of takeoffs and landings for a contiguous time slot of T minutes. The beginning of the time slot is time 0. The time when t minutes passed after the beginning of the time slot is time t. The end of the time slot is time T.
In the time slot, M airplanes will arrive at EGOI Airport. They are numbered from 1 to M. The (1 \le i \le M) will start landing at time A_{i}. But the runway used by airplane i is not yet fixed. It will be fixed by JOI-kun. The schedule for the takeoffs is not fixed at all. JOI-kun will decide the number of airplanes which will take off, the time of a takeoff of each airplane, and the runway used by it.
In summary, the schedule has to obey the following rules.
- It is not allowed that more than one airplane take off or land at the same time in the same runway. However, it is allowed that an airplane starts taking off or landing, just after another airplane finished taking off or landing in the same runway.
- All takeoffs and landings should be finished in the time slot of T minutes. Namely, it is not allowed for an airplane to start taking off or landing before time 0. It is not allowed for an airplane to finish taking off or landing after time T.
JOI-kun wants to arrange the schedule so that it obeys the above rules, and the number of airplanes which will take off is maximized.
Write a program which, given the number of runways, the number of airplanes which will land, the length of the time slot, the time required for a takeoff, the time required for a landing, and the time when each airplane will start landing, calculates the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, your program should report it.
Input
Read the following data from the standard input. Given values are all integers.
N M T K L
A_{1} A_{2} \cdots A_{M}
Output
Write one line to the standard output. The output should contain the maximum possible number of airplanes which will take off from EGOI Airport. If it is not possible to arrange the schedule so that it obeys the rules, output -1.
Constraints
- 1 \le N \le 100\,000.
- 1 \le M \le 100\,000.
- 1 \le T \le 1\,000\,000\,000 (= 10^{9}).
- 1 \le K \le T.
- 1 \le L \le T.
- 0 \le A_{i} \le T - L (1 \le i \le M).
Subtasks
- (7 points) N = 1.
- (12 points) N = 2, M \le 20.
- (17 points) N = 2, K = 2, L = 2.
- (28 points) N = 2.
- (11 points) N \le 100.
- (25 points) No additional constraints.
Sample Input 1
2 4 15 3 2 4 1 5 12
Sample Output 1
5
For example, if JOI-kun arranges the schedule as follows, 5 airplanes will take off.
- At time 0, an airplane will start taking off in the runway 1.
- At time 1, the airplane 2 will start landing in the runway 2.
- At time 4, the airplane 1 will start landing in the runway 2.
- At time 5, the airplane 3 will start landing in the runway 1.
- At time 6, an airplane will start taking off in the runway 2.
- At time 7, an airplane will start taking off in the runway 1.
- At time 9, an airplane will start taking off in the runway 2.
- At time 10, an airplane will start taking off in the runway 1.
- At time 12, the airplane 4 will start landing in the runway 2.
It is not possible to arrange the schedule so that it obeys the rules and more than 5 airplanes will take off. Therefore, output 5.
This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.
Sample Input 2
2 6 23 3 6 9 13 1 16 4 8
Sample Output 2
-1
It is not possible to arrange the schedule so that it obeys the rules. Therefore, output -1.
This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.
Sample Input 3
1 5 20 2 1 2 8 11 15 5
Sample Output 3
7
This sample input satisfies the constraints of Subtasks 1, 5, 6.
Sample Input 4
2 6 13 2 2 7 0 1 10 7 4
Sample Output 4
5
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.
Sample Input 5
4 4 14 2 3 5 6 3 9
Sample Output 5
21
This sample input satisfies the constraints of Subtasks 5, 6.
Sample Input 6
8 15 100 4 7 93 10 74 46 37 64 68 5 38 67 6 48 76 36 21
Sample Output 6
170
This sample input satisfies the constraints of Subtasks 5, 6.
配点 : 100 点
問題文
EGOI 空港には N 本の滑走路があり,1 から N までの番号が付けられている.この空港では,飛行機の離陸開始から終了まで K 分かかり,着陸開始から終了まで L 分かかる.この連続する K 分または L 分の間,飛行機は 1 つの滑走路を占有することになる.
EGOI 空港で働いている JOI 君は,ある T 分間の期間における離着陸のスケジュールを立てる仕事を任された.期間の開始時刻を時刻 0 とし,時刻 0 から t 分経過した時刻を時刻 t と表す.期間が終わるのは時刻 T である.
期間中に着陸するのは,1 から M まで番号付けられた M 機の飛行機である.飛行機 i (1 \leqq i \leqq M) は時刻 A_{i} に着陸を開始することが決まっているが,使用する滑走路はこれから JOI 君が決めることになっている.また,離陸のスケジュールは全く決められていないため,離陸する飛行機の数,各飛行機の離陸開始時刻と使用する滑走路はすべて JOI 君が決めることになる.
以上を踏まえて,スケジュールは以下のルールをすべて守るように作らなければならない.
- 1 つの滑走路で複数の飛行機が同時に離着陸を行っている状態にしてはならない.ただし,ある飛行機が離着陸を終えると同時に,同じ滑走路で別の飛行機が離着陸を開始することは許される.
- すべての離着陸は T 分間の期間中に行われなければならない.すなわち,時刻 0 より前に離着陸を開始したり,時刻 T より後に離着陸を終了したりしてはならない.
JOI 君はこのルールをすべて守ったうえで,できるだけ多くの飛行機が離陸できるようなスケジュールを立てたいと思った.
滑走路の数,着陸する飛行機の数,期間の長さ,離陸にかかる時間,着陸にかかる時間,各飛行機が着陸を開始する時刻が与えられたとき,期間中に EGOI 空港を離陸できる飛行機の数の最大値を求めるプログラムを作成せよ.ただし,ルールをすべて守ったスケジュールを作ることが不可能である場合は,そのことを報告せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M T K L
A_{1} A_{2} \cdots A_{M}
出力
標準出力に,期間中に EGOI 空港を離陸できる飛行機の数の最大値を 1 行で出力せよ.ただし,ルールをすべて守ったスケジュールを作ることが不可能である場合は,-1 を出力せよ.
制約
- 1 \leqq N \leqq 100\,000.
- 1 \leqq M \leqq 100\,000.
- 1 \leqq T \leqq 1\,000\,000\,000 (= 10^{9}).
- 1 \leqq K \leqq T.
- 1 \leqq L \leqq T.
- 0 \leqq A_{i} \leqq T - L (1 \leqq i \leqq M).
小課題
- (7 点) N = 1.
- (12 点) N = 2,M \leqq 20.
- (17 点) N = 2,K = 2,L = 2.
- (28 点) N = 2.
- (11 点) N \leqq 100.
- (25 点) 追加の制約はない.
入力例 1
2 4 15 3 2 4 1 5 12
出力例 1
5
例えば,以下のようなスケジュールを立てることで,5 機の飛行機が離陸することができる.
- 時刻 0 に,滑走路 1 で飛行機の離陸を開始する.
- 時刻 1 に,滑走路 2 で飛行機 2 の着陸を開始する.
- 時刻 4 に,滑走路 2 で飛行機 1 の着陸を開始する.
- 時刻 5 に,滑走路 1 で飛行機 3 の着陸を開始する.
- 時刻 6 に,滑走路 2 で飛行機の離陸を開始する.
- 時刻 7 に,滑走路 1 で飛行機の離陸を開始する.
- 時刻 9 に,滑走路 2 で飛行機の離陸を開始する.
- 時刻 10 に,滑走路 1 で飛行機の離陸を開始する.
- 時刻 12 に,滑走路 2 で飛行機 4 の着陸を開始する.
どのようなスケジュールを立てても,ルールをすべて守ったうえで 6 機以上が離陸することはできないため,5 を出力する.
この入出力例は小課題 2, 4, 5, 6 の制約を満たす.
入力例 2
2 6 23 3 6 9 13 1 16 4 8
出力例 2
-1
ルールをすべて守ったスケジュールを作ることが不可能であるため,-1 を出力する.
この入出力例は小課題 2, 4, 5, 6 の制約を満たす.
入力例 3
1 5 20 2 1 2 8 11 15 5
出力例 3
7
この入出力例は小課題 1, 5, 6 の制約を満たす.
入力例 4
2 6 13 2 2 7 0 1 10 7 4
出力例 4
5
この入出力例は小課題 2, 3, 4, 5, 6 の制約を満たす.
入力例 5
4 4 14 2 3 5 6 3 9
出力例 5
21
この入出力例は小課題 5, 6 の制約を満たす.
入力例 6
8 15 100 4 7 93 10 74 46 37 64 68 5 38 67 6 48 76 36 21
出力例 6
170
この入出力例は小課題 5, 6 の制約を満たす.