Hai Robot Thu Thập Quà

Dynamic Programming
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho bảng số không âm kích thước $N \times M$. Có hai robot: Robot 1 xuất phát ở góc trên trái $(1, 1)$ và Robot 2 xuất phát ở góc trên phải $(1, M)$. Ở mỗi bước, cả hai robot cùng đi xuống hàng tiếp theo; từ ô $(i, j)$, mỗi robot có thể đi tới $(i+1, j-1)$, $(i+1, j)$ hoặc $(i+1, j+1)$ (nếu hợp lệ). Khi kết thúc ở hàng $N$, nếu hai robot cùng đi qua một ô thì giá trị ô đó chỉ được tính một lần. Hãy tìm tổng giá trị lớn nhất cả hai robot thu thập được.

Dữ liệu vào
  • Dòng đầu: hai số nguyên dương $N, M$ $(1 \le N, M \le 70)$.
  • $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 giá trị lớn nhất có thể.
Ví dụ
Input Output
4 3\n3 1 1\n2 5 1\n1 5 5\n2 1 1 24
3 3\n1 0 0\n0 2 0\n0 0 3 6
Giới hạn
  • $1 \le N, M \le 70$
  • $0 \le a_{i,j} \le 10^9$
  • Thời gian: 1 giây
  • Bộ nhớ: 256 MB
Draft saved