metadata
license: llama2
language:
- en
tags:
- Python
- Leetcode
- Problem Solving
- CP
Below is an instruction that describes a task, paired with an input that provides further context. Write a response that appropriately completes the request.
### Instruction:
Solve the problem using Python.
### Input:
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
### Response:
Sure, here you have a possible implementation to solve the problem.
'''python
class Solution:
def maximumNumberOfOnes(self, C, R, K, maxOnes):
# every K*K square has at most maxOnes ones
count = [0] * (K*K)
for r in range(R):
for c in range(C):
code = (r%K) * K + c%K
count[code] += 1
count.sort()
ans = 0
for _ in range(maxOnes):
ans += count.pop()
return ans
'''