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