Vasya and matrix (Editorial)

Let $a$ be the input rectangular matrix. Create a two-dimensional array $dp$ of the same size, where dp[i][j] represents the sum of elements in the submatrix with opposite corners at points $(1,1)$ and $(i,j)$. The values in this array can be computed using the following formula:

Now consider a submatrix of array $a$ of size w \times h. Let its opposite corners be located at coordinates $(i,j)$ and (i + w - 1, j + h - 1).

Then the sum of all elements in the submatrix is calculated using the formula:

Let's solve the problem using brute-force search. Iterate over all possible submatrix sizes w \times h, as well as all valid coordinates of the top-left corner $(i,j)$ of the submatrix. Using the $dp$ array, compute the sum of elements inside the current submatrix in constant time. If this sum does not exceed $k$, we keep track of the maximum area among all such submatrices.

However, this brute-force approach has a time complexity of O(n^4), which is too slow. We can speed it up to O(n^3logn) by applying binary search on the width $h$ of the submatrix.

Fix the top-left corner $(i,j)$. Let g(w, h) denote the sum of elements in the submatrix with corners at $(i,j)$ and (i + w - 1, j + h - 1). If we fix the height $w$ and treat the width $h$ as a variable, then g(w, h) becomes a non-decreasing function with respect to $h$, since the original matrix $a$ contains non-negative integers. This allows us to use binary search to find the maximum value of $h$ for which g(w, h) \le k.

Example

For example, the sum of the numbers in the submatrix with corners at points $(2,2)$ and $(3,3)$ is

Algorithm implementation

The input matrix is stored in the array $a$.

#define MAX 210
int a[MAX][MAX], dp[MAX][MAX];

The function f(w, h) returns $1$ if there exists a submatrix of size w \times h such that the sum of its elements does not exceed $k$. To check this, all possible coordinates of the top-left corner $(i,j)$ are iterated over, and the sum of elements in the rectangle with corners at $(i,j)$ and (i + w - 1, j + h - 1) is computed in constant time using the $dp$ array.

int f(int w, int h)
{
  for (int i = 1; i + w - 1 <= n; i ++)
  for (int j = 1; j + h - 1 <= m; j ++)
    if (dp[i + w - 1][j + h - 1] - dp[i + w - 1][j - 1] –
        dp[i - 1][j + h - 1] + dp[i - 1][j - 1] <= k) return 1;
  return 0;
};

The main part of the program. Read the input matrix.

scanf("%d %d %d",&n,&m,&k);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  scanf("%d",&a[i][j]);

Based on the input matrix $a$, compute the auxiliary matrix $dp$.

for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
  dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];

Iterate over the possible values of the submatrix width $w$.

answer = 0;
for (w = 1; w <= n; w++)
{

The length of the submatrix is determined using binary search over the range [l; r].

  l = 1; r = m;
  while (l < r)
  {
    mid = (l + r) / 2;

For a submatrix of size w \times mid, iterate over all possible positions of its top-left corner $(i,j)$. If there exists at least one position where the sum of elements in the submatrix does not exceed $k$, update the value of the resulting area $answer$.

    if (f(w,mid))
    {
      answer = max(answer, w * mid);
      l = mid + 1;
    } 
    else r = mid;
  }

  mid = (l + r) / 2;
  if (f(w,mid))
    answer = max(answer, w * mid);
};

Print the area of the largest submatrix found.

printf("%d\n",answer);