準急電車 (Semiexpress)
题意翻译
### 题目描述
JOI 铁路公司是 JOI 国唯一的铁路公司。
在某条铁路沿线共有$n$个站点,依次编号为$1,2,\cdots, n$。当前有两种列车服役,分别是高速列车和普通列车。
- 普通列车每站都停,对于每一个$i(1\leq i < N)$,从站点$i$到站点$i+1$用时$A$分钟。
- 高速列车只在站点$S_1,S_2,\cdots,S_M(1=S_1<S_2<\cdots<S_M=N)$停车,对于每一个$i(1\leq i < N)$,从站点$i$到站点$i+1$用时$B$分钟。
JOI 铁路公司拟定开设第三类车次:准高速列车。对于每一个$i(1\leq i < N)$,从站点$i$到站点$i+1$用时$C$分钟。准高速列车停的站点还没有决定好,但是这些站点必须满足以下要求:
- 高速列车停的所有站点准高速列车都必须停。
- 准高速列车必须停恰好$K$个站点。
JOI 铁路公司想要最大化从$1$号站点在$T$分钟内可以到的站点数目(不计$1$号站点,不计等车和换乘时间)。JOI 铁路公司想要合理地安排站点使得这个数目最大。
当合理地安排准高速列车停的站点时,从$1$号站点出发在$T$分钟内抵达的站点($1$号站点不计)最多是多少?
### 输入格式
第一行三个整数$N,M,K$,意义如题面所示。
第二行三个整数$A,B,C$,意义如题面所示。
第三行一个整数$T$,意义如题面所示。
接下来$M$行,这$M$行中的第$i$行有一个整数$S_i$,表示快车停的站点。
### 输出格式
一行一个整数,表示答案。
### 样例解释 1
在这组数据中,一共有$10$个站点,快车停$1,6,10$三个站点。我们假设准快车停$1,5,6,8,10$五个站点,于是,在$2,3,\cdots,10$中,我们可以从$1$号站点在$30$分钟内抵达除了$9$号站点的所有站点。
对于某些$i$,从$1$号站点到$i$号站点最优的方案如下:
- 从$1$号站点到$3$号站点,只需要乘坐普通列车,时间为$20$分钟。
- 从$1$号站点到$7$号站点,先乘坐高速列车到站点$6$,然后转乘普通列车,时间为$25$分钟。
- 从$1$号站点到$8$号站点,先乘坐高速列车到站点$6$,然后转乘准高速列车,时间为$25$分钟。
- 从$1$号站点到$9$号站点,先乘坐高速列车到站点$6$,然后转乘准高速列车到站点$8$,再换乘普通列车,时间为$35$分钟。
### 数据范围
所有的数据满足以下条件:
$2\leq N\leq 10^9,2\leq M\leq K\leq 3000,K\leq N$
$1\leq B < C < A \leq 10^9,1\leq T\leq 10^{18}$
$1=S_1<S_2<\cdots<S_M=N$
子任务 $1(\texttt{18 pts})$
$N\leq 3000,K-M=2,A\leq 10^6,T\leq 10^9$
子任务 $2(\texttt{30 pts})$
$N\leq 300$
子任务 $3(\texttt{52 pts})$
无特殊限制。
题目描述
[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_b
输入输出格式
输入格式
標準入力から以下の入力を読み込め.
- $ 1 $ 行目には,$ 3 $ 個の整数 $ N,\ M,\ K $ が空白を区切りとして書かれている.これらは,JOI 鉄道に駅が $ N $ 個あり,急行電車は $ M $ 個の駅に停車し,準急電車は $ K $ 個の駅に停車することを表す.
- $ 2 $ 行目には,$ 3 $ 個の整数 $ A,\ B,\ C $ が空白を区切りとして書かれている.これらは,普通電車,急行電車,準急電車が隣り合う駅の間を走行するのにかかる時間がそれぞれ $ A $ 分,$ B $ 分,$ C $ 分であることを表す.
- $ 3 $ 行目には,整数 $ T $ が書かれている.これは,駅 $ 1 $ からの乗車時間の合計が $ T $ 分以内となる駅の個数を最大化したいことを表す.
- 続く $ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には,整数 $ S_i $ が書かれている.これは,急行電車が駅 $ S_i $ に停車することを表す.
输出格式
標準出力に,乗車時間の条件を満たす駅の個数の最大値を $ 1 $ 行で出力せよ.
- - - - - -
输入输出样例
输入样例 #1
10 3 5
10 3 5
30
1
6
10
输出样例 #1
8
输入样例 #2
10 3 5
10 3 5
25
1
6
10
输出样例 #2
7
输入样例 #3
90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90
输出样例 #3
2
输入样例 #4
12 3 4
10 1 2
30
1
11
12
输出样例 #4
8
输入样例 #5
300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
输出样例 #5
72
输入样例 #6
1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000
输出样例 #6
3000
说明
### 課題
JOI 鉄道の駅の個数,急行電車の停車駅,電車の速度の情報,乗車時間の条件が与えられたとき,乗車時間の条件を満たす駅の個数の最大値を求めるプログラムを作成せよ.
- - - - - -
### 制限
すべての入力データは以下の条件を満たす.
- $ 2\ \leqq\ N\ \leqq\ 1\,000\,000\,000 $.
- $ 2\ \leqq\ M\ \leqq\ K\ \leqq\ 3\,000 $.
- $ K\ \leqq\ N $.
- $ 1\ \leqq\ B\ <\ C\ <\ A\ \leqq\ 1\,000\,000\,000 $.
- $ 1\ \leqq\ T\ \leqq\ 10^{18} $.
- $ 1\ =\ S_1\ <\ S_2\ <\ \cdots\ <\ S_M\ =\ N $.
- - - - - -
### 小課題
#### 小課題 1 \[18 点\]
以下の条件を満たす.
- $ N\ \leqq\ 300 $.
- $ K\ -\ M\ =\ 2 $.
- $ A\ \leqq\ 1\,000\,000 $.
- $ T\ \leqq\ 1\,000\,000\,000 $.
#### 小課題 2 \[30 点\]
- $ N\ \leqq\ 300 $ を満たす.
#### 小課題 3 \[52 点\]
- 追加の制限はない.
- - - - - -
### Sample Explanation 1
この入力例では,JOI 鉄道には $ 10 $ 個の駅があり,急行電車は $ 3 $ 個の駅 $ 1,\ 6,\ 10 $ に停車する.準急電車を駅 $ 1,\ 5,\ 6,\ 8,\ 10 $ に停車させると,駅 $ 2,\ 3,\ \ldots,\ 10 $ のうち駅 $ 9 $ を除く $ 8 $ 個の駅に,駅 $ 1 $ から $ 30 $ 分以内の乗車時間で移動できる. 準急電車の停車駅を上記のように決めたときの,いくつかの $ i $ についての,駅 $ 1 $ から駅 $ i $ まで移動する際の乗車時間と,そのときの移動方法を示す. - 駅 $ 1 $ から駅 $ 3 $ へは,普通電車だけを用いて $ 20 $ 分の乗車時間で移動できる. - 駅 $ 1 $ から駅 $ 7 $ へは,駅 $ 1 $ から駅 $ 6 $ まで急行電車で移動し,駅 $ 6 $ で普通電車に乗り換えることで $ 25 $ 分の乗車時間で移動できる. - 駅 $ 1 $ から駅 $ 8 $ へは,駅 $ 1 $ から駅 $ 6 $ まで急行電車で移動し,駅 $ 6 $ で準急電車に乗り換えることで $ 25 $ 分の乗車時間で移動できる. - 駅 $ 1 $ から駅 $ 9 $ へは,駅 $ 1 $ から駅 $ 6 $ まで急行電車で移動し,駅 $ 6 $ から駅 $ 8 $ まで準急電車で移動し,駅 $ 8 $ から駅 $ 9 $ まで普通電車で移動することで $ 35 $ 分の乗車時間で移動できる. - - - - - -
### Sample Explanation 2
\- - - - - -
### Sample Explanation 3
\- - - - - -
### Sample Explanation 4
この入力例は,小課題 $ 1 $ の条件を満たさない. - - - - - -
### Sample Explanation 5
この入力例は,小課題 $ 1 $ の条件を満たさない. - - - - - -
### Sample Explanation 6
この入力例は,小課題 $ 1 $ および小課題 $ 2 $ の条件を満たさない.