Che Ô

Đ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

Có $N$ vị trí trên trục số cần được che. Một chiếc ô có độ rộng $W$ (che từ $x$ đến $x + W - 1$ ) có giá $C_{W}$ . Các ô có thể chồng lấp.

Hãy tìm chi phí tối thiểu để mua các ô che phủ tất cả $N$ vị trí.

Dòng 1: Hai số nguyên $N$ và $M$ ( $M$ là tọa độ lớn nhất)
$N$ dòng tiếp theo: Tọa độ mỗi vị trí cần che
$M$ dòng tiếp theo: $C_{1}, C_{2}, \dots, C_{M}$ — giá ô có độ rộng $1, 2, \dots, M$

Input	Output	Giải thích
6 12 1 2 11 8 4 12 2 3 4 4 8 9 15 16 17 18 19 19	9	Chi phí tối ưu: che nhóm vị trí liền nhau bằng các ô phù hợp

Bình luận

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