Mã bài:
mine
Điểm:
2,3 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Mandink là một người thợ đào vàng. Bản đồ mỏ vàng có dạng một bảng ~A~ kích thước ~M × N~ ~(1 ≤ M, N ≤ 1000)~, ở mỗi ô trên bảng có một số nguyên ~a_{i_j}~ ~(|a_{i_j}| ≤ 10^9)~ , giá trị dương khi đó là khối vàng, giá trị âm khi đó là khối đá).
Quy tắc đào vàng:
- Mandink xuất phát từ một trong ~M~ ô ở cột thứ nhất.
- Từ ô ~(i, j)~ chỉ được quyền sang một trong các ô ~(i, j+1); (i−1, j+1); (i+1, j+1)~.
- Đào vàng kết thúc khi Mandink đến một trong ~M~ ô ở cột cuối cùng.
Dữ liệu vào
- Dòng 1: Ghi hai số ~M, N~ là số hàng và số cột của bảng.
- ~M~ dòng tiếp theo: dòng thứ ~i~ ghi đủ ~M~ số trên hàng ~i~ của bảng theo đúng thứ tự từ trái qua phải.
Dữ liệu ra
Gồm ~1~ dòng duy nhất ghi tổng giá trị lớn nhất mà Mandink có thể đào được với quy tắc trên.
Sample Input
5 7
9 -2 6 2 1 3 4
0 -1 6 7 1 3 3
8 -2 8 2 5 3 2
1 -1 6 2 1 6 1
7 -2 6 2 1 3 7
Sample Output
41
Bình luận