Khai Thác Mỏ Vàng
Points
42
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Một mỏ vàng được biểu diễn bằng lưới $N \times M$, ô $(i, j)$ chứa $a_{i,j}$ lượng vàng. Người thợ mỏ bắt đầu từ bất kỳ ô nào ở cột 1 và đi sang cột $M$. Từ ô $(i, j)$, người thợ có thể di chuyển sang $(i-1, j+1)$, $(i, j+1)$ hoặc $(i+1, j+1)$ (nếu hợp lệ). Hãy tìm lượng vàng tối đa có thể thu hoạch.
Dữ liệu vào
- Dòng đầu: hai số nguyên dương $N, M$ $(1 \le N, M \le 1000)$.
- $N$ dòng tiếp theo: mỗi dòng gồm $M$ số nguyên không âm $a_{i,j}$ $(0 \le a_{i,j} \le 10^9)$.
Dữ liệu ra
- In ra tổng lượng vàng tối đa thu hoạch được.
Ví dụ
| Input | Output |
|---|---|
| 3 3\n1 3 3\n2 1 4\n0 6 4 | 12 |
| 4 4\n10 33 13 15\n22 21 4 1\n5 0 2 3\n0 6 14 2 | 83 |
Giới hạn
- $1 \le N, M \le 1000$
- $0 \le a_{i,j} \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion