CTDL&GT bài 26.A17 CTDL&GT bài Maximum Path Sum.


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Maximum Path Sum.

Cho bảng A[] kích thước N x M (N hàng, M cột). Bạn được phép đi xuống dưới, đi sang phải và đi xuống ô chéo dưới về bên phải. Khi đi qua ô (i, j), điểm nhận được bằng A[i][j]. Hãy tìm đường đi từ ô (1, 1) tới ô (N, M) sao cho tổng điểm là lớn nhất.

Input Format

Dòng 1 gồm số nguyên dương N và M; N dòng tiếp theo, mỗi dòng gồm M số nguyên A[i][j].(1<=N,M<=500; 1<=A[i][j]<=1000)

Constraints

.

Output Format

In ra kết quả của bài toán.

Ví dụ:

Dữ liệu vào
4 4
41 67 34 0
69 24 78 58
62 64 5 45
81 27 61 91
Dữ liệu ra
432

Comments

There are no comments at the moment.

Zalo