Code : Select Cells in Grid With Maximum Score

class Solution {
  public:
    int maxScore(vector<vector<int>> &grid);
};

int Solution::maxScore(vector<vector<int>> &mat) {
    int n = mat.size();

    // present_in[ele] contains all rows that have an element equal to 'ele'.
    map<int, set<int>> present_in;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < mat[i].size(); j++) {
            present_in[mat[i][j]].insert(i);
        }
    }

    int full_mask = (1 << n) - 1;
    vector<int> dp(full_mask + 1, 0);
    for (auto &[val, rows] : present_in) {
        vector<int> ndp = dp;
        for (int mask = 0; mask <= full_mask; mask++) {
            for (int i = 0; i < n; i++) {
                if ((1 << i) & mask) {
                    continue;
                }
                if (!rows.count(i)) {
                    continue;
                }
                int nxt = mask | (1 << i);
                ndp[nxt] = max(ndp[nxt], dp[mask] + val);
            }
        }
        swap(dp, ndp);
    }
    return *max_element(dp.begin(), dp.end());
}