---
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
'''
```