PreVOI 2025 - Thử nghiệm
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice đã chế tạo một robot thông minh và muốn thử nghiệm khả năng tìm đường của robot trên một lưới ô vuông kích thước ~m \times n~. Các hàng của lưới được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô giao giữa hàng ~i~ ~(1 \le i \le m)~, cột ~j~ ~(1 \le j \le n)~ gọi là ô ~(i, j)~ và có ~d_{ij}~ viên kim cương. Sẽ có ~q~ lần thử nghiệm độc lập, lần thử nghiệm thứ ~t~ ~(1 \le t \le q)~ được mô tả bằng ô ~(x_t, y_t)~. Cụ thể, robot xuất phát tại ô ~(1, 1)~ tìm đường di chuyển đến ô ~(m, n)~, mỗi lượt robot chỉ được đi sang ô kề bên phải hoặc ô kề bên dưới và không đi vào ô ~(x_t, y_t)~, khi robot ở ô nào, robot sẽ thu thập hết kim cương tại ô đó, robot cần thu thập được nhiều kim cương nhất.
Yêu cầu: Với mỗi lần thử nghiệm, hãy giúp Alice tính số viên kim cương mà robot có thể thu thập được.
Input
Dòng đầu tiên chứa ba số nguyên ~m, n, q~ ~(2 < m \times n \le 3 \cdot 10^5; q \le m \times n-2)~;
Dòng thứ ~i~ ~(1 \le i \le m)~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên không âm ~d_{i1}, d_{i2}, \dots, d_{in}~ ~(d_{ij} \le 10^9)~;
Dòng thứ ~t~ ~(1 \le t \le q)~ trong ~q~ dòng tiếp theo chứa hai số nguyên dương ~x_t, y_t~ ~(1 \le x_t \le m; 1 \le y_t \le n)~. Chú ý, ô ~(x_t, y_t)~ khác ô ~(1, 1)~ và ô ~(m, n)~.
Output
- Gồm ~q~ dòng, dòng thứ ~t~ ~(1 \le t \le q)~ chứa một số nguyên tương ứng là số viên kim cương mà robot có thể thu thập được trong lần thử nghiệm thứ ~t~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~m, n \le 40~ |
| 2 | ~40\%~ | ~m, n \le 400~ |
| 3 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
4 5 2
0 0 0 0 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 1
1 2
2 2
Sample Output 1
3
2
Bình luận