Hành trình không quá hai bước

Buổi 24 — Mock Contest Phase 1
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho bảng lưới kích thước $R \times C$, ô $(i, j)$ chứa giá trị nguyên $G_{i,j}$ (có thể âm). Bạn xuất phát tại ô $(1, 1)$ và muốn đi tới ô $(R, C)$. Tại mỗi bước, bạn chỉ được phép đi xuống dưới (từ $(i, j)$ sang $(i+1, j)$) hoặc sang phải (từ $(i, j)$ sang $(i, j+1)$).

Tuy nhiên, để tránh mất thăng bằng, bạn không được phép đi quá $2$ bước liên tiếp theo cùng một hướng (tức là không có $3$ bước liên tiếp đều đi xuống, hoặc $3$ bước liên tiếp đều đi sang phải).

Hãy tìm tổng giá trị lớn nhất các ô đi qua (bao gồm cả $(1, 1)$ và $(R, C)$), hoặc in ra IMPOSSIBLE nếu không có đường đi hợp lệ.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $R, C$ ($1 \le R, C \le 500$).
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $G_{i,j}$ ($-10^9 \le G_{i,j} \le 10^9$).
Dữ liệu ra
  • Một số nguyên duy nhất là tổng lớn nhất, hoặc IMPOSSIBLE nếu không đi được.
Ví dụ
Input Output
3 3
1 2 3
4 5 6
7 8 9
29
1 4
1 2 3 4
IMPOSSIBLE
Giới hạn
  • $1 \le R, C \le 500$.
  • $-10^9 \le G_{i,j} \le 10^9$.
Draft saved