Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.5 kB
1
Indexable
Never
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