RECT
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
RECT
Cho bảng số \(A\) nguyên không âm gồm \(m \times n\) phần tử. Các dòng của lưới được đánh số từ \(1\) đến \(m\), từ trên xuống dưới. Các cột của lưới được đánh số từ \(1\) đến \(n\), từ trái sang phải. Ô nằm trên giao của dòng \(i\) và cột \(j\) của lưới gọi là ô \((i, j)\) được điền số \(a_{i,j}\). Ta định nghĩa trọng số của một hình chữ nhật con có tọa độ từ \((x, y)\) đến \((u, v)\) là:
\[
W_{(x,y,u,v)} = \min_{\substack{i=x \to u \\ j=y \to v}} \{a_{i,j}\} \times \sum_{\substack{i=x \to u \\ j=y \to v}} a_{i,j}
\]
Yêu cầu: Tìm hình chữ nhật con có trọng số lớn nhất.
Input
- Dòng đầu là số \(m, n\) (\(m, n \le 500\));
- \(m\) dòng sau, dòng thứ \(i\) chứa \(n\) số nguyên \(a_{i,1}, a_{i,2}, \dots, a_{i,n}\) (\(a_{i,j} \le 10^6\)).
Output
- Gồm một dòng chứa một số nguyên là trọng số lớn nhất tìm được.
Example
Test 1
Input
3 4
1 2 3 4
1 2 3 4
1 2 3 4Output
63Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019
Bình luận (1)