前書き: この問題に \(300^3 \times \log_2(300) \approx 2.2 \times 10^8\) といった時間計算量で正解するには、定数倍にかなり気を遣わなければならないか不可能かのどちらかです。なので、この解説ではなるべく \(300^3\) の計算量でこの問題を解くことを考えます。実際、この計算量で解くことが可能です。

\(1 \le A_i \le 300\) という特徴的な制約に着目してみましょう。
\(f(R) = \) ( \(R\) 内のマスに書かれた整数の総和 ) \(\times\) ( \(R\) 内のマスに書かれた整数の最小値 ) と書き表せることを思い出しましょう。
思い切って、 \(2\) つめの項である \(R\) 内のマスに書かれた整数の最小値 \(m\) を固定することを考えてみましょう。この時、固定の仕方は \(1\) から \(300\) までの \(300\) 通り試せば十分です。

更に、長方領域のうち最も下の行も固定してしまいましょう。これは \(N\) 通り試せば十分です。

ここで、以下の値を考えます。

• \(H_{i,j} = \) ( \(i\) 行目を最も下の行としたときに、最小値が \(m\) 以上であるという条件のもとで \(j\) 列目をどれだけ上に伸ばせるか? )

この \(H_{i,j}\) が大きい順に列を ( \(M\) 回 ) 追加していくことを考えます。

ある列を追加した時に、その左右に連続して既に追加されている列の極大な広がりに着目します。このとき、それらの列は ( \(j\) 列目がボトルネックとなって) 必ず \(H_{i,j}\) だけ上に伸ばせ、またそれを超えて上に伸ばすことはできません。
このとき、極大な長方領域に含まれる整数の和は二次元累積和によって \(O(1)\) で取得可能であり、長方領域に含まれる整数の最小値は \(m\) 以上です。
これにより、最小値が \(m\) 以上となる極大な領域を調べ尽くすことができます。

「左右に連続して既に追加されている列の極大な広がりに着目する」を連結リストの要領で処理したり、列を \(H_{i,j}\) の降順にソートする際に \(H_{i,j} = H_{i-1,j}+1\) または \(H_{i,j}=0\) が成り立つことを利用したりすると、余計な \(\log\) が付くことを回避できます。詳細は実装例も参照してください。

以上から、この問題を \(O(NM \max A_i)\) で解くことができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int sum2d(int fx,int fy,int tx,int ty,vector<vector<int>> &s){
  if(fx>tx || fy>ty){return 0;}
  if(fx==0 && fy==0){return s[tx][ty];}
  else if(fx==0){
    return s[tx][ty]-s[tx][fy-1];
  }
  else if(fy==0){
    return s[tx][ty]-s[fx-1][ty];
  }
  else{
    return s[tx][ty]-s[tx][fy-1]-s[fx-1][ty]+s[fx-1][fy-1];
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;
  cin >> n >> m;
  vector<vector<int>> a(n,vector<int>(m));
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin >> a[i][j];
    }
  }
  vector<vector<int>> s=a;
  for(int i=1;i<n;i++){
    for(int j=0;j<m;j++){s[i][j]+=s[i-1][j];}
  }
  for(int i=0;i<n;i++){
    for(int j=1;j<m;j++){s[i][j]+=s[i][j-1];}
  }

  long long res=0;
  for(int mi=1;mi<=300;mi++){
    vector<pair<int,int>> vp(m);
    for(int i=0;i<m;i++){
      vp[i].first=0;
      vp[i].second=i;
    }

    for(int i=0;i<n;i++){
      vector<pair<int,int>> top,bot;
      for(auto &nx : vp){
        if(a[i][nx.second]>=mi){
          top.push_back({nx.first+1,nx.second});
        }
        else{
          bot.push_back({0,nx.second});
        }
      }
      vp.clear();
      for(auto &nx : top){vp.push_back(nx);}
      for(auto &nx : bot){vp.push_back(nx);}

      vector<int> lef(m),rig(m);
      for(int j=0;j<m;j++){
        lef[j]=j-1;
        rig[j]=j+1;
      }

      for(auto &nx : vp){
        int cl=lef[nx.second];
        int cr=rig[nx.second];
        if(cl>=0){rig[cl]=cr;}
        if(cr<m){lef[cr]=cl;}
        long long cf=sum2d(i-nx.first+1,cl+1,i,cr-1,s);
        cf*=mi;
        res=max(res,cf);
      }
    }
  }
  cout << res << "\n";
  return 0;
}