JOI 2017 - Semiexpress - LQDOJ: Le Quy Don Online Judge

JOI 2017 - Semiexpress

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 2100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đường sắt JOI có \(N\) ga được đánh số từ \(1\) đến \(N\) dọc theo một tuyến đường. Hiện có tàu nhanh và tàu thường.

Tàu thường dừng tại mọi ga và mất \(A\) phút để đi giữa hai ga liên tiếp. Tàu nhanh chỉ dừng tại \(S_1,S_2,\ldots,S_M\), trong đó

\[ 1=S_1<S_2<\cdots<S_M=N, \]

và mất \(B\) phút để đi giữa hai ga liên tiếp.

Đường sắt JOI dự định vận hành tàu bán nhanh, mất \(C\) phút giữa hai ga liên tiếp. Các ga dừng của tàu bán nhanh phải gồm mọi ga tàu nhanh dừng và có đúng \(K\) ga.

Đường sắt JOI muốn chọn các ga dừng sao cho số ga khác ga \(1\) có thể đến từ ga \(1\) trong không quá \(T\) phút là lớn nhất. Không tính thời gian tàu dừng. Chỉ được đi theo chiều số ga tăng dần; tại một ga mà nhiều loại tàu cùng dừng, hành khách có thể chuyển giữa các tàu đó.

Hãy tính số ga lớn nhất có thể đến trong giới hạn thời gian.

Dữ liệu vào

Dòng đầu chứa \(N,M,K\).
Dòng thứ hai chứa \(A,B,C\).
Dòng thứ ba chứa \(T\).
\(M\) dòng tiếp theo lần lượt chứa \(S_1,S_2,\ldots,S_M\); mỗi số nằm trên một dòng.

Dữ liệu ra

In số ga lớn nhất thỏa mãn điều kiện thời gian.

Ràng buộc

\(2\le N\le 1\,000\,000\,000\).
\(2\le M\le K\le 3\,000\) và \(K\le N\).
\(1\le B<C<A\le 1\,000\,000\,000\).
\(1\le T\le 10^{18}\).
\(1=S_1<S_2<\cdots<S_M=N\).

Phân nhóm

\(18\) điểm: \(N\le 300\), \(K-M=2\), \(A\le 1\,000\,000\), \(T\le 1\,000\,000\,000\)
\(30\) điểm: \(N\le 300\)
\(52\) điểm: Không có ràng buộc bổ sung

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Nếu tàu bán nhanh dừng tại \(1,5,6,8,10\), ta đến được mọi ga từ \(2\) đến \(10\) trừ ga \(9\) trong \(30\) phút. Đến ga \(3\) bằng tàu thường mất \(20\) phút. Đến ga \(7\) bằng tàu nhanh tới ga \(6\) rồi tàu thường mất \(25\) phút. Đến ga \(8\) bằng tàu nhanh tới ga \(6\) rồi tàu bán nhanh cũng mất \(25\) phút. Đến ga \(9\) nhanh nhất mất \(35\) phút: tàu nhanh tới \(6\), tàu bán nhanh tới \(8\), rồi tàu thường tới \(9\).

Ví dụ 2

Input

Output

Ví dụ 3

Input

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90

Output

Ví dụ 4

Input

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1.

Ví dụ 5

Input

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1.

Ví dụ 6

Input

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000

Output

Giải thích

Ví dụ này không thỏa mãn ràng buộc của nhóm 1 hoặc nhóm 2.

Nguồn

JOI 2016/2017, Vòng chung kết.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2016/2017 - Vòng chung kết (2 Tháng 1., 2017)