leetcode

0 class Solution {

1 public:

2 int maximumRows(const vector<vector<int>> &matrix, const int numSelect) const {

3 const int n = size(matrix), m = size(matrix[0]);

4 unordered_map<uint16_t, int> um;

5

6 for (int i = 0; i < n; i++) {

7 uint16_t crnt = 0, cnt = 0;

8 for (int j = 0; j < m; j++) {

9 crnt |= matrix[i][j] << j;

10 cnt += matrix[i][j];

11 }

12 if (cnt > numSelect) continue;

13 um[crnt]++;

14 }

15

16 uint16_t res = 0, crnt = (1 << numSelect) - 1;

17 while (crnt <= 1 << m) {

18 uint16_t count = 0;

19 for (const auto [k, v] : um) {

20 if ((k & ~crnt) == 0) count += v;

21 }

22 res = max(res, count);

23

24 uint16_t t = crnt | (crnt - 1);

25 crnt = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(crnt) + 1));

26 }

27

28 return res;

29 }

30 };