TLEoj Contest #03 - Đường đi ma trận

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

HoBaoPhuc2009

Dạng bài

Bạn được cho một ma trận tam giác bậc $n$ . Cụ thể là ma trận sẽ có định dạng như sau:

$a_{1,1}$

$a_{2,1}\ a_{2,2}$

$a_{3,1}\ a_{3,2}\ a_{3,3}$

$\dots$

$a_{n,1}\ a_{n,2}\ a_{n,3}\dots a_{n,n}$

Tại ô $(i,j)$ sẽ có giá trị là $a_{i,j}$ . Bạn bắt đầu xuất phát từ đỉnh $(1,1)$ . Mỗi lượt bạn có thể di chuyển đến ô $(i+1,j)$ hoặc ô $(i+1,j+1)$ . Nhiệm vụ của bạn là tìm một đường đi từ ô xuất phát đến đích là bất cứ ô nào ở hàng $n$ sao cho tổng giá trị của tất cả các ô trên đường đi (tính cả ô xuất phát và kết thúc) là lớn nhất có thể

Input, Output và Subtasks

Input

Dòng đầu tiên gồm một số nguyên dương $n$ là bậc của ma trận $(1\le n\le 1000)$
Sau đó là $n$ dòng, dòng thứ $i$ bao gồm $i$ giá trị $a_{i,1},a_{i,2},\dots,a_{i,i}$ ( $|a_{i,j}|\le 100$ ). Các giá trị nhập vào được cách nhau bởi một dấu khoảng trắng

Output

Một dòng duy nhất ghi kết quả của bài toán.

Sample

Input

Output

Note

Đường đi tối ưu: $(1,1)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (4,2)\rightarrow (5,2)$ . Tổng là $7+3+8+7+5=30$

Bình luận

Không có bình luận nào.