Gian - An
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: duytoannguyenledh

Trên một lưới ô vuông hình chữ nhật MxN, tại mỗi ô (i; j) của lưới ta đặt một lượng thức ăn dành cho gián, tương ứng với số nguyên dương aij . Từ ô hiện tại, gián có thể bò đến một trong 2 ô khác để ăn hết lượng thức ăn đặt ở ô đó là: ô kề cạnh bên phải và ô kề cạnh bên dưới. Ban đầu chú gián ở vị trí ô (1;1) và giả thiết ô này không chứa thức ăn.

Yêu cầu:

Hãy xác định lộ trình trong lưới của gián sao cho từ ô xuất phát đi đến ô cuối cùng (M; N), gián có thể ăn được một lượng thức ăn nhiều nhất.

Dữ liệu vào:

Dòng đầu ghi hai số nguyên dương M và N (0<M,N £ 100). M dòng tiếp theo, mỗi dòng thứ i, ghi N số nguyên dương  aij (0£aij £ 100; i = 1..M; j = 1..N)

Dữ liệu ra: 

Đưa ra màn hình một số nguyên, là lượng thức ăn lớn nhất mà gián có thể ăn được.

Ví dụ

  • input
    4 5
    0 5 1 3 4
    6 1 9 1 5
    1 1 1 4 1
    1 3 4 6 3
    output
    30
  • input
    4 5
    0 1 2 3 1
    0 2 3 4 5
    6 1 2 3 1
    3 2 4 1 5
    output
    21
Back to Top