Untitled
class Solution { public: using ll = long long; long long maximumValueSum(vector<vector<int>>& board) { int m = board.size(), n = board[0].size(); priority_queue<pair<int, pair<int, int>>>pq; //unordered_map<int, multiset<int>>row, col; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ pq.push({board[i][j], {i, j}}); //row[i].insert(board[i][j]); //col[j].insert(board[i][j]); } } ll ans = INT_MIN; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ unordered_set<int>r, c; r = {i}, c = {j}; ll tmp_val = board[i][j], cnt = 0; vector<pair<int, pair<int, int>>>v; while(!pq.empty() && cnt < 2){ auto tmp = pq.top(); v.push_back(tmp); pq.pop(); if(r.count(tmp.second.first) || c.count(tmp.second.second)) continue; tmp_val += tmp.first; r.insert(tmp.second.first); c.insert(tmp.second.second); cnt++; } ans = max(ans, tmp_val); for(auto ele: v){ pq.push(ele); } } } return ans; } };
Leave a Comment