Following Directions

Điểm: 1,00 (OI)

Giới hạn thời gian: 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

Nông dân John quản lý một lưới $(N + 1) \times (N + 1)$ . Mỗi ô $(i, j)$ với $1 \leq i, j \leq N$ chứa một con bò và một biển chỉ hướng (sang phải R hoặc xuống dưới D). Các ô ở hàng dưới cùng và cột phải nhất (trừ góc) chứa máng thức ăn với chi phí cho trước.

Mỗi ngày, các con bò đi theo biển chỉ hướng cho đến khi gặp máng thức ăn. Trước mỗi ngày cho ăn, một biển chỉ hướng bị đổi chiều. Tính tổng chi phí cho ăn ban đầu và sau mỗi lần đổi.

Dữ liệu vào

Dòng đầu: số nguyên $N$ ( $1 \leq N \leq 1500$ )
$N$ dòng tiếp: xâu $N$ ký tự (R hoặc D) và chi phí máng ở cột phải nhất
Dòng tiếp: $N$ chi phí máng ở hàng dưới cùng
Dòng tiếp: số nguyên $Q$ ( $1 \leq Q \leq 1500$ )
$Q$ dòng tiếp: tọa độ $(i, j)$ của biển cần đổi

Dữ liệu ra

$Q + 1$ dòng: tổng chi phí ban đầu, sau đó chi phí sau mỗi lần đổi.

Ràng buộc

$1 \leq N \leq 1500$ , $1 \leq Q \leq 1500$
$1 \leq$ chi phí $\leq 500$
Giới hạn thời gian: 8 giây

Ví dụ

Input	Output	Giải thích
2 RR 1 DD 10 100 500 4 1 1 1 1 1 1 2 1	602 701 602 701 1501	Ban đầu: bò ở (1,1),(1,2),(2,1),(2,2) có chi phí 1,1,100,500 (tổng 602). Đổi (1,1) từ R sang D: bò (1,1) đến máng chi phí 100, tổng 701.

Bình luận

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