Điểm:
100
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một bảng A kích thước n x m ô, trên mỗi ô ghi một số nguyên dương là số lượng quà mà một con robot cần mang đi. Con robot xuất phát tại một ô A[i,1] nào đó của cột i (1 ≤ i ≤ n) cần di chuyển sang một ô lân cận của cột j (1 ≤ j ≤ m). Cụ thể, từ ô A[i, j], con robot chỉ được di chuyển sang một trong ba ô sau: A[i, j+1], A[i-1, j+1], A[i+1, j+1] và khi con robot đi qua ô nào thì mang theo toàn bộ lượng quà ở ô đó.
Yêu cầu: Hãy tìm đường đi cho con robot từ một ô nào đó của cột 1 đến một ô nào đó của cột m để cho tổng lượng quà mà con robot cần mang đi là lớn nhất.
Dữ liệu vào
- Dòng một ghi 2 số nguyên n và m cách nhau ít nhất một dấu cách (1 ≤ n, m ≤ 1000).
- Dòng thứ i trong n dòng tiếp theo ghi m số nguyên dương, mỗi số không vượt quá \(10^{5}\) và hai số liên tiếp cách nhau ít nhất một dấu cách.
Dữ liệu ra
- Gồm một dòng là tổng các số chứa trong các ô mà con robot đã đi qua.
Giới hạn
- 50% số test ứng với 1 ≤ n, m ≤ 500;
- 30% số test ứng với 500 < n, m ≤ 800;
- 20% số test ứng với 800 < n, m ≤ 1000.
Ví dụ
Input
3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1
Output
61
Bình luận
như này có gọi là chatgpt không mấy ad:
Có