C++ * 400ms * beats 100% * Track Duplicates
Intuition\n Describe your first thoughts on how to solve this problem. \nDP won\'t work, look at the constraints once, I got TLE @ 1487 cases.\nThis problem req
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDP won\'t work, look at the constraints once, I got TLE @ 1487 cases.\nThis problem requires Greedy approach.\n# Approach\n<!-- Describe your approach to solving the problem. --> \n1. Sort profit in descending order and take first k profits including duplicate categories.\n2. Now we can maximazie distinct_categories by adding them into set and removing lowest duplicate items from set\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```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);\n        sort(items.begin(), items.end(), [&](vector<int> &a, vector<int> &b){\n            return a[0] > b[0];\n        });\n        long long n = items.size(), ans = 0, curr = 0;\n        stack<int> dups;\n        unordered_set<int> s;\n        for(int i = 0; i < n; i++){\n            if(i < k){\n                curr += items[i][0];\n                if(s.count(items[i][1])) dups.push(items[i][0]);\n                else s.insert(items[i][1]);\n            }\n            else if(!s.count(items[i][1]) && !dups.empty()){\n                s.insert(items[i][1]);\n                curr -= dups.top();\n                dups.pop();\n                curr += items[i][0];\n            }\n            long long t = s.size();\n            ans = max(ans, curr + t*t);\n        }\n        return ans;\n    }\n};\n```
['Stack', 'Sorting', 'Ordered Set', 'C++']