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.

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        unordered_map<int, int> freq;
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                freq[((i % sideLength) * sideLength + (j % sideLength))]++;
            }
        }
        priority_queue<int> pq;
        for(auto& [_, c] : freq)
            pq.push(c);
        int res = 0;
        while(!pq.empty() and maxOnes) {
            res += pq.top(); pq.pop();
            maxOnes--;
        }
        return res;
    }
};