l179. One More Grid Task - Extreme - 高中生程式解題系統

內容

原題，和本題的差異只有執行時間限制 $(TL)$ 以及 $A_{i, j}$ 的大小。

有一個 $N \times M$ 的網格，其中第 $i, j$ 格裡面的數字為 $A_{i, j}$ ，現在需要你從這裡面找一個長方形區塊 $R$ ，並且定義 $f (R)$ 代表「區塊 $R$ 裡面所有數字中的最小數字 $\times$ 區塊 $R$ 中的數字的總和」，請你讓 $f (R)$ 盡可能的大，並求出這個 $f (R)$ ?

輸入說明

第一行有兩個正整數，代表 $N, M$ 。

接著有 $N$ 行，每行有 $M$ 個數，第 $i$ 行中的第 $j$ 個數代表 $A_{i, j}$ 。

同一行的多個整數中間都以空白隔開。

$1 \leq N, M \leq 300$
$1 \leq A_{i, j} \leq 10^{6}$

輸出說明

輸出一個正整數，代表 $f (R)$ 的最大值。注意答案可能超過 $2^{31}$ 。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1

範例輸出 #3

範例輸入 #4

2 2
48763 48763
48763 48763

範例輸出 #4

9511320676

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

$100 %$ : 無其他限制

Problem prepared by r1cky

標籤:

stack 單調隊列枚舉

出處:

AtCoder [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」