Goldilocks và N con bò

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Goldilocks quản lý một trang trại có $N$ con bò. Mỗi con bò $i$ có một khoảng nhiệt độ thoải mái từ $A_{i}$ đến $B_{i}$ . Khi nhiệt kế trong chuồng được đặt ở nhiệt độ $T$ :

Nếu $T < A_{i}$ : con bò $i$ sản xuất $X$ đơn vị sữa (quá lạnh).
Nếu $A_{i} \leq T \leq B_{i}$ : con bò $i$ sản xuất $Y$ đơn vị sữa (thoải mái).
Nếu $T > B_{i}$ : con bò $i$ sản xuất $Z$ đơn vị sữa (quá nóng).

Biết rằng $Y > X$ và $Y > Z$ . Hãy tìm lượng sữa tối đa có thể thu được bằng cách chọn nhiệt độ $T$ (số nguyên) một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên: bốn số nguyên $N$ , $X$ , $Y$ , $Z$ .
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $A_{i}$ và $B_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất: lượng sữa tối đa có thể thu được.

Ràng buộc

$1 \leq N \leq 20 000$
$0 \leq X, Y, Z \leq 1 000$ , $Y > X$ , $Y > Z$
$0 \leq A_{i} \leq B_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 7 9 6 5 8 3 4 13 20 7 10	31	Đặt $T = 7$ hoặc $T = 8$ : bò 1 và bò 4 thoải mái ( $9$ mỗi con), bò 2 quá nóng ( $6$ ), bò 3 quá lạnh ( $7$ ). Tổng $= 9 + 6 + 7 + 9 = 31$ .
25 5 7 3 3 6 5 7 3 5 2 6 1 9 2 7 0 9 3 6 0 6 2 6 1 8 7 9 0 2 2 3 5 7 2 9 2 8 7 9 3 6 1 2 3 9 1 9 4 7 4 8 0 5	159	Chọn nhiệt độ tối ưu để tối đa hóa số bò thoải mái.

Ghi chú

Nhiệt độ $T$ phải là số nguyên nhưng có thể là bất kỳ giá trị nào (không giới hạn trong khoảng nào cụ thể).

Bình luận

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