Đường Đi Chi Phí Nhỏ Nhất

Đ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

Cho một lưới $N \times M$ ô. Bạn xuất phát từ ô $(1, 1)$ và muốn đến các ô $(x_{i}, y_{i})$ theo yêu cầu truy vấn. Từ ô $(x, y)$ , bạn có thể thực hiện hai loại di chuyển:

Di chuyển sang phải $(x, y) \to (x, y + 1)$ : chi phí $x^{2}$
Di chuyển xuống $(x, y) \to (x + 1, y)$ : chi phí $c_{y}$

trong đó $c_{y}$ là chi phí di chuyển xuống ở cột $y$ , cho trước.

Với mỗi truy vấn $(x_{i}, y_{i})$ , hãy tìm chi phí nhỏ nhất để đi từ $(1, 1)$ đến $(x_{i}, y_{i})$ .

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $M$
Dòng 2: $M$ số nguyên $c_{1}, c_{2}, \dots, c_{M}$
Dòng 3: số nguyên $Q$ — số lượng truy vấn
$Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $x_{i}$ và $y_{i}$

Dữ liệu ra

In $Q$ dòng, mỗi dòng là chi phí nhỏ nhất cho truy vấn tương ứng.

Ràng buộc

$2 \leq N \leq 10^{9}$
$2 \leq M \leq 2 \times 10^{5}$
$1 \leq c_{y} \leq 10^{9}$
$1 \leq Q \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq N$ , $1 \leq y_{i} \leq M$
Đáp án luôn vừa trong kiểu số nguyên 64-bit

Ví dụ

Input	Output	Giải thích
5 4 1 100 100 20 20 1 1 2 1 3 1 4 1 5 1 1 2 2 2 3 2 4 2 5 2 1 3 2 3 3 3 4 3 5 3 1 4 2 4 3 4 4 4 5 4	0 1 2 3 4 1 5 11 19 29 2 9 20 35 54 3 13 29 49 69	Chi phí di chuyển xuống ở 4 cột lần lượt là $1, 100, 100, 20$ . Ví dụ: để đến $(5, 4)$ với chi phí $69$ , đường đi tối ưu là $(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4) \to (4, 4) \to (5, 4)$ với tổng chi phí $1 + 1 + 9 + 9 + 9 + 20 + 20 = 69$ .

Bình luận

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