Bẫy Kiện Cỏ (Bronze)

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ kiện cỏ đặt tại các vị trí khác nhau trên một con đường thẳng. Mỗi kiện cỏ $j$ có kích thước $S_{j}$ và vị trí $P_{j}$ .

Bessie bắt đầu tại một điểm không có kiện cỏ và có thể di chuyển tự do, nhưng không thể đi qua kiện cỏ. Ngoại lệ: nếu Bessie chạy liên tục $D$ đơn vị theo một hướng, cô có thể phá vỡ bất kỳ kiện cỏ nào có kích thước nghiêm ngặt nhỏ hơn $D$ . Sau khi phá vỡ, kiện cỏ biến mất và Bessie có thể mở rộng không gian để tấn công các kiện khác.

Bessie thoát được nếu cô phá được qua kiện cỏ ngoài cùng bên trái hoặc bên phải. Tính tổng chiều dài các vị trí xuất phát từ đó Bessie không thể thoát.

Dữ liệu vào

Dòng 1: Số nguyên $N$ .
$N$ dòng tiếp theo: kích thước $S_{j}$ và vị trí $P_{j}$ của từng kiện cỏ.

Dữ liệu ra

Tổng chiều dài các vùng không thể thoát.

Ràng buộc

$1 \leq N \leq 4000$
$1 \leq S_{j}, P_{j} \leq 10^{9}$ , các vị trí đôi một phân biệt.

Ví dụ

Input	Output	Giải thích
5 8 1 1 4 8 8 7 15 4 20	14	Không thể thoát từ các khoảng tổng chiều dài 14
12 23 113 24 210 25 62 23 90 24 36 41 245 23 146 24 96 23 186 24 207 24 80 25 212	77

Bình luận

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