Giúp minh với
Có một chú kiến bò đi kiếm ăn trên sân trường. Sân trường có kích thước MxN và được chia thành m hàng n cột đều nhau. Các hàng được đánh số 1 đến m từ trên xuống dưới, các cột được đánh số 1 đến n từ trái sang phải.
Mỗi ô trên sân trường có chứa một số lượng thức ăn nhất định. Chú kiến có thể xuất phát vào một ô bất kỳ của hàng 1 và muốn bò xuống hàng m. Với mỗi bước đi, nếu chú đang ở ô (i,j) thì chú kiến chỉ có thể bò sang 1 trong 3 ô kề là (i+1,j-1), (i+1,j), (i+1,j+1).
Bạn hãy giúp cho chú kiến tìm một đường đi từ hàng 1 xuống hàng m sao cho lượng thức ăn mà chú ăn được trên đường đi là nhiều nhất.
Dữ liệu nhập:
- Dòng đầu gồm hai số nguyên m và n là kích thước sân trường (1 ≤ m, n ≤ 1000)
- m dòng tiếp theo mỗi dòng gồm n số nguyên mô tả lượng thức ăn có trên các ô của sân trường. Số lượng thức ăn trên mỗi ô của sân trường là một số nguyên không âm có giá trị không quá 109.
Kết quả:
- in ra một số nguyên duy nhất là số lượng thức ăn lớn nhất kiến ta lấy được.
Ví dụ
input output
3 4 21
9 2 3 1
4 5 6 1
7 2 1 1
Loga
Sinh Học lớp 12
