Easy C++ solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThink Greedy. Take top K elements and find the ans. Now, what factors affect the final 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThink Greedy. Take top K elements and find the ans. Now, what factors affect the final ans? The distinct categories and value of ith element. We just need to optimally choose the elements which increase our ans.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nRemember: `answer = sumOfValues + distinctCategories^2`\nSort the items array in decreasing order of profit.\n\nChoose first K values from items. A variable `currVal` is used to keep the sum of the profit of these  values. Here we tried to maximize the `sumOfValues`.\n\nWhenever you encounter a `category` or `items[i][1]` for the first time, just create an instance of it in map. \nIf it has been encountered before, we push the profit of the item associated with category to the stack. The top of this stack denotes "The item with minimum profit value whose category is already present in the subsequence". Why do we need this? Suppose an item comes later on i.e., `i>=k`, then if the category of that item has not been seen before, then it can possibly increase our answer. To maximize our answer, we just need to try to increase `distinctCategories`. On encountering a new category, we will remove the element with minimum profit with a duplicate category i.e, value at top of the stack.\n\nNow run the loop from i>=k and do the above mentioned steps. Note, you cannot add an element in a subsequence of length k if there are no elements with duplicate categoreis., i.e stack is empty. Moreover, you can only add replace a element with a new element only when the category of the new element is unseen. \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe sorting taken O(nlogn).\nThe rest operations are O(n).\nInsertions in unorderd_map is on avg O(1) and same with lookup.\nHence the `total time taken : O(nlogn);`\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n) for map and for stack it will be maximum of \nO(k-1). So the `total space complexity is O(n)`.\n\n# Code\n```\nclass Solution {\npublic:\n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        sort(items.begin(),items.end(),[](const auto &a, const auto &b){\n            return a[0]>b[0];\n        });\n\n        unordered_map<int,int> ump;\n        stack<int> st;\n        long long ans = 0,currVal = 0;\n        for(int i=0;i<k;i++){\n            currVal += items[i][0];\n            if(ump.find(items[i][1])==ump.end()){\n                //First encounter\n                ump[items[i][1]]++;\n            }else{\n                //push it into the stack\n                st.push(items[i][0]);\n            }\n        }\n        long long sz = ump.size();\n        ans = max(ans,currVal + 1LL*sz*sz);\n        for(int i=k;i<items.size();i++){\n            if(st.empty()){\n                continue;\n            }\n            if(ump.find(items[i][1])!=ump.end()){\n                continue;\n            }\n            //the ith item\'s category should be unseen to add it to the list\n            //if it is seen then we have already taken a \n            //instance of profit with a greater value\n\n            currVal+=(items[i][0]-st.top());\n            st.pop();\n            ump[items[i][1]]++;\n            sz = ump.size();\n            ans = max(ans, currVal+1LL*sz*sz);\n        }\n        return ans;\n    }\n};\n```
['C++']