Bò nhảy Pogo

Đ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

Bessie dùng gậy nhảy pogo để nhảy trên một đường thẳng. Trên đường thẳng có $N$ mục tiêu, mục tiêu thứ $i$ nằm tại vị trí $x_{i}$ và cho $p_{i}$ điểm.

Bessie bắt đầu tại một mục tiêu bất kỳ và chỉ di chuyển theo một hướng (sang trái hoặc sang phải). Mỗi bước nhảy phải có khoảng cách ít nhất bằng bước nhảy trước đó (bước nhảy đầu tiên có thể có khoảng cách bất kỳ). Bessie thu được điểm từ tất cả các mục tiêu mà cô đáp xuống (bao gồm cả mục tiêu bắt đầu).

Hãy tìm tổng điểm lớn nhất mà Bessie có thể thu được.

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ .
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_{i}$ và $p_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất: tổng điểm lớn nhất.

Ràng buộc

$1 \leq N \leq 1000$
$0 \leq x_{i} \leq 10^{6}$
$1 \leq p_{i} \leq 10^{6}$
Các vị trí $x_{i}$ đôi một khác nhau.

Ví dụ

Input	Output	Giải thích
6 5 6 1 1 10 5 7 6 4 8 8 10	25	Sắp xếp theo vị trí: (1,1), (4,8), (5,6), (7,6), (8,10), (10,5). Đường đi tối ưu đi sang phải: 4 $\to$ 5 $\to$ 7 $\to$ 10, thu được $8 + 6 + 6 + 5 = 25$ điểm. Khoảng cách các bước: 1, 2, 3 (tăng dần).
8 4 91 97 93 62 33 74 85 8 29 81 32 12 67 25 3	283	Sắp xếp theo vị trí: (4,91), (8,29), (12,67), (25,3), (62,33), (74,85), (81,32), (97,93). Bessie chọn đường đi tối ưu theo một hướng với khoảng cách bước nhảy không giảm để đạt tổng điểm 283.

Bình luận

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