Hành trình không quá hai bước
Points
22
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
IMPOSSIBLEnế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$.
Community Discussion