Tiệc Buffet của Bessie (Silver)

Đ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$ ô cỏ trong một cánh đồng, mỗi ô có chất lượng $Q_{i}$ phân biệt. Bessie bắt đầu tại bất kỳ ô nào và có thể di chuyển giữa các ô liền kề, với chi phí $E$ năng lượng mỗi bước.

Khi ăn cỏ ở ô chất lượng $Q$ , Bessie nhận được $Q$ năng lượng. Quy tắc: sau khi ăn cỏ chất lượng $Q$ , cô chỉ được ăn tiếp ở ô có chất lượng lớn hơn $Q$ . Cô có thể đi qua các ô mà không ăn.

Tìm năng lượng tối đa Bessie có thể tích lũy (năng lượng nhận từ ăn cỏ trừ chi phí di chuyển).

Dữ liệu vào

Dòng đầu: $N$ và $E$
$N$ dòng tiếp theo: chất lượng $Q_{i}$ , số hàng xóm $D_{i}$ , rồi $D_{i}$ chỉ số ô hàng xóm

Dữ liệu ra

Năng lượng tối đa Bessie có thể tích lũy.

Ràng buộc

$1 \leq N \leq 1000$
$1 \leq E \leq 10^{6}$
$1 \leq Q_{i} \leq 10^{6}$ (các $Q_{i}$ phân biệt)
$D_{i} \leq 10$

Ví dụ

Input	Output	Giải thích
5 2 4 1 2 1 3 1 3 4 6 2 2 5 5 2 2 5 2 2 3 4	7	Bessie ăn ô 4 (+5), đi 2 bước đến ô 3, ăn ô 3 (+6), tổng = 5+6-2×2 = 7.
5 1 10 1 2 3 2 1 3 8 1 4 15 2 3 5 5 1 4	25	Bessie ăn ô 2 (+3), đi 3 bước đến ô 5 ăn (+5), đi 2 bước đến ô 3 ăn (+8), đi 1 bước đến ô 4 ăn (+15). Tổng = 3+5-3+8-2+15-1 = 25.

Bình luận

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