0.Hình chữ nhật lớn nhất

Submit solution
Points: 3 (partial)
Time limit: 0.347s
Memory limit: 20M
Author:
themiscscvn
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho ma trận vuông có kích thước N x N. Các hàng của mỗi ma trận được đánh số từ 1 đến N từ trên xuống dưới. Các cột của mỗi ma trận được đánh số từ 1 đến N từ trái sang phải. Phần tử ở hàng i, cột j của ma trận A được ký hiệu là A[i,j]. Nhiệm vụ của bạn là tìm một hình chữ nhật trong ma trận có cạnh song song với cạnh của ma trận sao cho tổng các phần tử trong hình chữ nhật là lớn nhất (Hình chữ nhật có kích thước nhỏ nhất là 1 x 1 và lớn nhất là N x N).

Input:

Dòng 1: số N (1 <= N <= 100)

N dòng tiếp theo, mỗi dòng chứa N số mà số thứ j là giá trị A[i,j] (-127 <= A[i,j] <= 127).

Output:

Tổng lớn nhất tìm được.

Example:

Input

 7
 9  5  2  0 -9  5  0 
 5  8 -2  0  0  4  7 
 7 -5  8 -1 -1 -6  5 
-6  4  4 -6  0  9 -2 
-6  9 -5 -5  0  0  0 
 1 -8  0 -6 -4 -5  5 
 3  2  4 -6  1  3  3

Output

44

Comments