Cod sursa(job #2766683)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 2 august 2021 20:48:19
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("teren.in");
ofstream fout("teren.out");

const int MAXN = 3e2;
int dp[1 + MAXN][1 + MAXN];

int get_sum(int x1, int y1, int x2, int y2) {
  return dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
}

void max_self(int &x, int y) {
  if (x < y)
    x = y;
}

int main() {
  int n, m, X;
  fin >> n >> m >> X;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      fin >> dp[i][j];
      dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    }
  int ans = 0;
  for (int l1 = 1; l1 <= n; ++l1)
    for (int l2 = l1; l2 <= n; ++l2) {
      int l = 1;
      for (int r = 1; r <= m; ++r) {
        while (get_sum(l1, l, l2, r) > X)
          ++l;
        max_self(ans, (l2 - l1 + 1) * (r - l + 1));
      }
    }
  fout << ans << '\n';
  fin.close();
  fout.close();
  return 0;
}