Matrix Product Submatrices

Problem Statement

Matrix Product Submatrices Given a matrix A[1..N][1..M] of integers, the product of a submatrix of A is the product of all the elements of the submatrix. Write an algorithm to find the number of non-empty submatrices that contain the top left element of matrix A (i.e. submatrices B[1..X][1..Y] for 1 ≤ X ≤ N, 1 ≤ Y ≤ M) with a product ≤ K. Input Format The first line consists of two space-separated integers - rows and columns , representing the number of rows in the matrix (N) and the number of columns in the matrix (M), respectively. The next N lines consist of M space-separated integers representing the elements of the matrix A. The last line consists of an integer - maxK , representing the maximum permissible product of the elements of a submatrix (K). Output Format Print an integer representing the number of submatrices that contain the top left element of the given matrix with a product less than or equal to K. Constraints 1 ≤ rows, columns ≤ 1000 0 ≤ maxK ≤ 10 6 0 ≤ X ≤ 1000, wher