Phủ sóng Wifi

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $N$ con bò đứng tại các vị trí phân biệt trên trục số. Cần đặt các trạm wifi để phủ sóng tất cả các bò. Một trạm có bán kính $r$ đặt tại $x$ phủ sóng mọi điểm trong $[x - r, x + r]$ , chi phí là $A + B \cdot r$ (với $r \geq 0$ ).

Tìm chi phí nhỏ nhất để phủ sóng tất cả các bò.

Dữ liệu vào

Dòng $1$ : Ba số nguyên $N$ , $A$ , $B$ ( $1 \leq N \leq 2000$ , $0 \leq A, B \leq 1000$ ).
$N$ dòng tiếp: Vị trí mỗi con bò (số nguyên trong $[0, 10^{6}]$ ).

Dữ liệu ra

Chi phí nhỏ nhất (có thể là số thực, in chính xác).

Ràng buộc

$1 \leq N \leq 2000$
$0 \leq A, B \leq 1000$
Vị trí bò trong $[0, 10^{6}]$

Ví dụ

Input	Output	Giải thích
3 20 5 7 0 100	57.5	Đặt trạm tại 3.5 bán kính 3.5 (chi phí 37.5) và tại 100 bán kính 0 (chi phí 20). Tổng 57.5.
10 702 626 65098 84355 39226 94653 67498 49319 51022 80722 28539 12572	7020

Bình luận

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