C++ Solution
Approach\n Describe your approach to solving the problem. \nSort all items according to profit from greatest to least.\n\nEnumerate the first K items, and if an
# Approach\n<!-- Describe your approach to solving the problem. -->\nSort all items according to profit from greatest to least.\n\nEnumerate the first K items, and if an item\'s category has already appeared before, push the profit of that item into a priority queue.\n\nYou want to enumerate the rest of the items, and if an item has a category which hasn\'t been seen before, you want to replace the current item with an item in the priority queue, such that you have more distinct category. From the priority queue, you obtain the item with the least profit.\n\n# Complexity\n- Time complexity: $O(n\\log n)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(n)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nusing ll = long long;\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        sort(items.begin(), items.end(), [](vector<int>& a, vector<int>& b) {\n            return a[0] > b[0];\n        });\n        unordered_set<int> vis;\n        priority_queue<int, vector<int>, greater<int> > heap;\n        ll tot = 0;\n        for(int i = 0;i<k;++i) {\n            auto x = items[i];\n            if(vis.count(x[1])) heap.push(x[0]);\n            else vis.insert(x[1]);\n            tot += x[0];\n        }\n        ll ans = tot + (ll)vis.size() * (ll)vis.size();\n        for(int i = k;i<items.size();++i) if(!heap.empty()) {\n            auto x = items[i];\n            if(!vis.count(x[1])) {\n                vis.insert(x[1]);\n                tot -= heap.top(); heap.pop();\n                tot += x[0];\n                ans = max(ans, tot + (ll)vis.size() * (ll)vis.size());\n            }\n        }\n        return ans;\n    }\n};\n```
['C++']