\(A_{i,j}\)の範囲が \(\leq10^9\) などでもカルテシアン木を使うことで \(O(NM^2)\) などで解くことができます。
実装も公式解に比べてとりわけ重くはありません。

長方形領域 \(R\) の \(l_y, r_y\) を全探索することを考えます。
\(l_y, r_y\) を定めた上で、各 \(x (1\leq x \leq n)\) について \([l_y,r_y]\) における区間和と区間minを求め、数列 \(B_i, C_i (1\leq i \leq n)\) とみなします。

すると、 \((\sum_{l \leq i \leq r}B_i) × ( \min_{l \leq i \leq r}C_i) \) が最大となるような区間 \([l,r]\)（これはすなわち\([l_x,r_x]\)です）を求めるという問題に帰着できます。
解釈としては、横に絞り込んで1列にしてから縦に絞り込むようなイメージです。

帰着後の問題はカルテシアン木上のDPなどで \(O(N)\) で解くことができます。カルテシアン木を使う場合、\(C_i\)について構築、葉から区間和の列\(B_i\)の和を求めていき、各ノード上で区間minの列\(C_i\)と掛け合わせてmaxを取ることで最終的な値が求まります。

計算量に関して、 \(l_y, r_y\) の全探索に \(O(M^2)\)、各ループ内のカルテシアン木の構築とDFSで\(O(N)\)、区間和と区間minは逐次計算や累積和などを利用することで \(O(1)\) 相当で求めることができます。 これより、 \(O(NM^2)\)で解けました。
ただし、定数倍/メモリの確保/再帰などが重めで、あまり非効率な実装だと通らない可能性があります。

例
https://atcoder.jp/contests/abc311/submissions/43887906 (1687ms)
https://atcoder.jp/contests/abc311/submissions/43888724 (簡単な範囲で高速化したもの: 798ms)