File size: 1,534 Bytes
d1b4b56 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
---
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
'''
``` |