Greedy + Heap, Select Profit Top-K Then Replace Duplicate Categories
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    // simplified code, after contest\n    long long findMaximumEleganceSimplified(vector<vector<int>>& items, int k) {\n        int n = items.size();\n        \n        sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);\n        });\n        \n        long long ans = 0, sum = 0;\n        // selected categories\n        unordered_set<int> chosen;\n        priority_queue<vector<int>, vector<vector<int>>, greater<>> toReplace;\n        int i = n - 1;\n        for (; i >= n - k; i--) {\n            int pro = items[i][0], cat = items[i][1];\n            if (chosen.count(cat)) {\n                toReplace.push(items[i]);\n            } else {\n                chosen.insert(cat);\n            }\n            \n            sum += pro;\n        }\n        \n        ans = sum + 1LL * chosen.size() * chosen.size();\n        while (i >= 0 && !toReplace.empty()) {\n            int pro = items[i][0], cat = items[i][1];\n            if (chosen.find(cat) == chosen.end()) {\n                sum -= toReplace.top()[0]; toReplace.pop();\n                sum += pro;\n\n                chosen.insert(cat);\n                long long candi = sum + 1LL * chosen.size() * chosen.size();\n                ans = max(ans, candi);\n            }\n            \n            i--;\n        }\n        \n        return ans;\n    }\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        // return findMaximumEleganceSimplified(items, k);\n\n        int n = items.size();\n        \n        sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);\n        });\n        \n        long long ans = 0, sum = 0;\n        // category -> profit in decresing\n        unordered_map<int, vector<vector<int>>> table;\n        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;\n        int i = n - 1;\n        for (; i >= n - k; i--) {\n            int pro = items[i][0], cat = items[i][1];\n            table[cat].push_back(items[i]);\n            \n            sum += pro;\n        }\n        \n        int keys = table.size(), dup = 0;\n        ans = sum + 1LL * keys * keys;\n        for (auto it = table.begin(); it != table.end(); it++) {\n            if (it->second.size() > 1) {\n                // duplicate category items in profit top-k\n                dup += it->second.size() - 1;\n                minHeap.push(it->second.back());\n                it->second.pop_back();\n            }\n        }\n        \n        while (i >= 0 && dup > 0) {\n            int pro = items[i][0], cat = items[i][1];\n            if (table.find(cat) == table.end()) {\n                sum -= minHeap.top()[0];\n                sum += pro;\n                \n                int idx = minHeap.top()[1]; minHeap.pop();\n                if (table[idx].size() > 1) {\n                    minHeap.push(table[idx].back());\n                    table[idx].pop_back();\n                }\n                \n                table[cat].push_back(items[i]);\n                keys++;\n                \n                ans = max(ans, sum + 1LL * keys * keys);\n                dup--;\n            }\n            \n            i--;\n        }\n        \n        return ans;\n    }\n};\n```
['C++']