Người soát vé tinh quái

Điểm: 8,00 (OI)

Giới hạn thời gian: 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Tuyến xe buýt có $n$ trạm trên một đường thẳng, tọa độ $0 = x_{1} < x_{2} < \dots < x_{n}$ . Mỗi ngày có $m$ hành khách: hành khách thứ $i$ lên xe ở trạm $a_{i}$ và xuống ở trạm $b_{i}$ ( $a_{i} < b_{i}$ ). Giá vé thông thường từ trạm $a$ đến trạm $b$ là $x_{b} - x_{a}$ .

Tuy nhiên, người soát vé có thể chọn tối đa một đoạn liên tiếp trên hành trình của hành khách để không bán vé. Cụ thể, anh ta chọn hai trạm $C, D$ với $a \leq C \leq D \leq b$ và chỉ bán vé cho hai đoạn $[a, C]$ và $[D, b]$ (nếu $C = D$ thì coi như bán vé bình thường, không có đoạn nào bỏ qua). Số tiền tiết kiệm được là $x_{D} - x_{C}$ , và hành khách cùng người soát vé chia đôi số tiền này (mỗi bên nhận $\frac{x_{D} - x_{C}}{2}$ ).

Trên đoạn giữa trạm $i$ và trạm $i + 1$ có thể có thanh tra với xác suất $p_{i} %$ (các đoạn độc lập với nhau). Nếu có thanh tra trên một đoạn mà hành khách không có vé cho đoạn đó, người soát vé bị phạt $c$ rúp cho mỗi hành khách như vậy.

Người soát vé muốn chọn $(C, D)$ cho từng hành khách một cách độc lập sao cho kỳ vọng tổng lợi nhuận của mình là lớn nhất. Hãy tính giá trị kỳ vọng tối đa này.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m$ , $c$ .
Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .
Dòng thứ ba chứa $n - 1$ số nguyên $p_{1}, p_{2}, \dots, p_{n - 1}$ .
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_{i}$ , $b_{i}$ .

Dữ liệu ra

In ra một số thực — kỳ vọng lợi nhuận lớn nhất của người soát vé. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{- 6}$ .

Ràng buộc

$2 \leq n \leq 150 000$
$1 \leq m \leq 300 000$
$1 \leq c \leq 10 000$
$0 \leq x_{i} \leq 10^{9}$ , $x_{1} = 0$ , $x_{i} < x_{i + 1}$
$0 \leq p_{i} \leq 100$
$1 \leq a_{i} < b_{i} \leq n$

Ví dụ

Input	Output	Giải thích
3 3 10 0 10 100 100 0 1 2 2 3 1 3	90.000000000	Hành khách 1 và 3 mua vé từ trạm 1 đến trạm 2. Hành khách 2 không mua vé. Đoạn 1–2 luôn có thanh tra nhưng cả hai vé đều có hiệu lực ở đó. Đoạn 2–3 không bao giờ có thanh tra nên hành khách 2 trốn vé thành công. Tổng lợi nhuận $= 0 + 90 / 2 + 90 / 2 = 90$ .
2 1 50 0 10 0 1 2	5.000000000	Đoạn duy nhất không bao giờ bị thanh tra, người soát vé bỏ qua bán vé và được chia $10 / 2 = 5$ .

Bình luận

Không có bình luận tại thời điểm này.