Tập Luyện

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một bảng số nguyên không âm kích thước $n \times m$ , ô $(i, j)$ có giá trị $a_{i, j}$ .

Có hai người di chuyển trong bảng:

Người 1 xuất phát tại ô $(1, 1)$ và kết thúc tại ô $(n, m)$ . Tại mỗi bước, từ ô $(i, j)$ người này có thể đi đến $(i + 1, j)$ hoặc $(i, j + 1)$ .
Người 2 xuất phát tại ô $(n, 1)$ và kết thúc tại ô $(1, m)$ . Tại mỗi bước, từ ô $(i, j)$ người này có thể đi đến $(i, j + 1)$ hoặc $(i - 1, j)$ .

Hai người phải gặp nhau tại đúng một ô trên bảng. Ô gặp nhau này không được tính giá trị cho bất kỳ ai. Tất cả các ô khác mà ít nhất một trong hai người đi qua (bao gồm ô xuất phát và ô kết thúc của mỗi người) đều được cộng vào tổng giá trị, mỗi ô tính tối đa một lần.

Hãy chọn đường đi của hai người sao cho tổng giá trị thu được là lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
$n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên mô tả bảng giá trị.

Dữ liệu ra

Một số nguyên duy nhất là tổng giá trị lớn nhất thu được.

Ràng buộc

$3 \leq n, m \leq 1000$
$0 \leq a_{i, j} \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
3 3 100 100 100 100 1 100 100 100 100	800	Hai người gặp nhau tại ô $(2, 2)$ . Người 1 đi $(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3)$ , người 2 đi $(3, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (1, 3)$ . Ô $(2, 2)$ không được tính, tổng giá trị là $8 \times 100 = 800$ .
3 3 1 10 1 1 10 1 1 10 1	26	Ô gặp nhau tốt nhất là $(2, 2)$ với một người đi dọc và một người đi ngang.
3 3 0 0 0 0 100 0 0 0 0	0	Mọi đường đi đều buộc một trong hai người phải đi qua ô $(2, 2)$ , nhưng ô gặp nhau không được tính nên tổng luôn bằng $0$ .

Bình luận

Không có bình luận tại thời điểm này.