Trò chơi nhảy ô trên lưới

Buổi 36 — DP on DAG & Profile DP Dynamic Programming
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

An và Bình chơi một trò chơi trên bảng lưới kích thước $R \times C$. Mỗi ô $(i, j)$ có điểm số $a_{i,j}$ và bước nhảy $d_{i,j} \ge 1$. Ban đầu có một quân cờ đặt ở ô $(1, 1)$. Hai người luân phiên đi (An đi trước):

  • Ở mỗi lượt, người chơi di chuyển quân cờ từ ô hiện tại $(i, j)$ sang ô $(i + d_{i,j}, j)$ hoặc $(i, j + d_{i,j})$ (nếu ô đích nằm trong bảng).
  • Nếu không thể di chuyển đi đâu được nữa, trò chơi kết thúc và điểm chung cuộc là giá trị $a_{i,j}$ tại ô dừng cuối cùng.

An muốn điểm chung cuộc lớn nhất có thể, còn Bình muốn điểm chung cuộc nhỏ nhất có thể. Giả sử cả hai đều chơi tối ưu, hãy tìm điểm chung cuộc của trò chơi.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $R, C$.
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên là bảng $a_{i,j}$.
  • $R$ dòng cuối cùng, mỗi dòng chứa $C$ số nguyên là bảng $d_{i,j}$.
Dữ liệu ra
  • In ra một số nguyên là điểm chung cuộc khi cả hai chơi tối ưu.
Ví dụ
Input Output
2 2\n1 5\n3 2\n1 1\n1 1 2
Giới hạn
  • $1 \le R, C \le 500$
  • $-10^6 \le a_{i,j} \le 10^6$
  • $1 \le d_{i,j} \le \max(R, C)$
Draft saved