1183.

Maximum Number of Ones

Hard

Consider a matrix M with dimensions width * height, such that every cell has value 0 or 1, and any square sub-matrix of M of size sideLength * sideLength has at most maxOnes ones. Return the maximum possible number of ones that the matrix M can have. Example 1: Input: width = 3, height = 3, sideLength = 2, maxOnes = 1 Output: 4 Explanation: In a 3*3 matrix, no 2*2 sub-matrix can have more than 1 one. The best solution that has 4 ones is: [1,0,1] [0,0,0] [1,0,1] Example 2: Input: width = 3, height = 3, sideLength = 2, maxOnes = 2 Output: 6 Explanation: [1,0,1] [1,0,1] [1,0,1] Constraints: 1 <= width, height <= 100 1 <= sideLength <= width, height 0 <= maxOnes <= sideLength * sideLength