1183. Maximum Number of Ones

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`

1183. Maximum Number of Ones
``````struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
fn maximum_number_of_ones(width: i32, height: i32, side_length: i32, max_ones: i32) -> i32 {
let width = width as usize;
let height = height as usize;
let side_length = side_length as usize;
let max_ones = max_ones as usize;
let mut queue: BinaryHeap<Reverse<usize>> = BinaryHeap::new();
for i in 0..side_length {
for j in 0..side_length {
let rows = 1 + (height - (i + 1)) / side_length;
let cols = 1 + (width - (j + 1)) / side_length;
queue.push(Reverse(rows * cols));
if queue.len() > max_ones {
queue.pop();
}
}
}
queue.into_iter().map(|t| t.0).sum::<usize>() as i32
}
}

#[test]
fn test() {
let width = 3;
let height = 3;
let side_length = 2;
let max_ones = 1;
let res = 4;
assert_eq!(
Solution::maximum_number_of_ones(width, height, side_length, max_ones),
res
);
let width = 3;
let height = 3;
let side_length = 2;
let max_ones = 2;
let res = 6;
assert_eq!(
Solution::maximum_number_of_ones(width, height, side_length, max_ones),
res
);
}
``````