グリッドに含まれる面積がちょうど \(K\) となる長方形の数を考えましょう。
左上のマスを固定して、高さが高々 \(N\) 通りしかないと考えると、個数は高々 \(N^2M\) と見積もられます(実際は面積を \(K\) とできないケースが多数存在するので、これよりも大幅に減少します)
粗く見積もっても \(200^3\) 個しか長方形がないため、長方領域に対する書き込まれた整数の和を長方形ひとつあたり \(O(1)\) で求められればこの問題に正解できます。

どのようにすればよいでしょうか？

グリッドの長方領域に書かれた整数の和を高速に求めるには、 二次元累積和 を用いるとよいです。

方法の概略を説明します。

• 最初に、元のグリッド \(A_{i,j}\) を用意する。
• まず、横方向に累積和を取る。 \(A_{i,j+1}\) に \(A_{i,j}\) を加算する行為を \(j\) の昇順に繰り返す。
• 次に、横方向に累積和を取る。 \(A_{i+1,j}\) に \(A_{i,j}\) を加算する行為を \(i\) の昇順に繰り返す。
• そうすると、 \(A_{i,j}\) に入った値がグリッドの左上からマス \((i,j)\) にかけての長方領域の総和となる。

その結果、 \((xl,yl)\) が左上、 \((xr,yr)\) が右下となる長方領域の総和は以下の手続きで求められます。

• \(A_{xr,yr}\) を加算。
• \(A_{xl-1,yr}\) を減算。
• \(A_{xr,yl-1}\) を減算。
• \(A_{xl-1,yl-1}\) を加算。

こうすることで、ちょうど欲しい長方領域の総和が得られることを(図を書いてみるなどして)確認してください。

あとは、左上のマスを固定して長方形を全探索することでこの問題に実行時間制限に対して余裕を持って正解することができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int sum2d(int xl,int yl,int xr,int yr,vector<vector<int>> &s){
  int res=0;
  res+=s[xr][yr];
  res-=s[xl-1][yr];
  res-=s[xr][yl-1];
  res+=s[xl-1][yl-1];
  return res;
}

int main(){
  int N,M,K;
  cin >> N >> M >> K;
  vector<vector<int>> s(N+1,vector<int>(M+1,0));
  for(int i=1;i<=N;i++){
    string S;
    cin >> S;
    for(int j=1;j<=M;j++){
      s[i][j]=(S[j-1]-'0');
    }
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      s[i][j]+=s[i][j-1];
    }
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      s[i][j]+=s[i-1][j];
    }
  }

  vector<pair<int,int>> vp;
  for(int h=1;h<=200;h++){
    if(K%h==0 && (K/h)<=200){
      vp.push_back({h,K/h});
    }
  }

  int res=-1;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      for(auto &nx : vp){
        int ir=i+nx.first-1;
        int jr=j+nx.second-1;
        if(ir<=N && jr<=M){
          res=max(res,sum2d(i,j,ir,jr,s));
        }
      }
    }
  }
  cout << res << "\n";
  return 0;
}