Explained Greedy | Clean Code | 19ms
IntuitionBalance between maximizing profit and distinct category count by first prioritizing unique categories, then swapping low-profit unique items with high-
# Intuition
Balance between maximizing profit and distinct category count by first prioritizing unique categories, then swapping low-profit unique items with high-profit duplicates.

# Approach
1. **Sort items by profit** (descending) to prioritize high-value items
2. **First phase**: Greedily select items with distinct categories to maximize the distinct_categories² term
   - Keep track of used positions, categories, total profit, and distinct category count
3. **Second phase**: Optimize by swapping
   - Add high-profit items with duplicate categories to reach k items
   - Calculate elegance after each addition
   - Remove the lowest-profit distinct category item to make room for more swaps
   - Repeat until no more beneficial swaps can be made
4. **Key insight**: Sometimes replacing a low-profit unique category item with a high-profit duplicate can increase overall elegance, despite reducing distinct_categories²

# Complexity
- Time complexity: **O(N log N)**
  - Dominated by sorting operation
  - The two-phase algorithm runs in O(N) time

# Code
```cpp []
class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        const int N = items.size();
        vector<pair<long long, int>> prof_cat(N);
        ::transform(items.begin(), items.end(), prof_cat.begin(),
                    [](const auto& pc) { return make_pair(pc[0], pc[1] - 1); });
        // Greedy approach:
        ::sort(prof_cat.begin(), prof_cat.end(), ::greater<pair<long long, int>>());

        vector<bool> pos2used(N);
        vector<bool> cat2used(N);
        // First phase: Greedily take items with distinct categories
        int small_dist_end = 0;
        int used_count = 0;
        long long sum_profit = 0;
        for (; small_dist_end < N && used_count < k; ++small_dist_end) {
            if (!cat2used[prof_cat[small_dist_end].second]) {
                cat2used[prof_cat[small_dist_end].second] = true;
                ++used_count;
                pos2used[small_dist_end] = true;
                sum_profit += prof_cat[small_dist_end].first;
            }
        }
        long long distinct_count = used_count;

        long long res = sum_profit + distinct_count * distinct_count;

        // Second phase: Try to improve by swapping
        // Key insight: We can replace low-profit distinct-category items with
        // high-profit duplicate-category items to potentially increase elegance
        for (int big_dupl_beg = 0; big_dupl_beg < small_dist_end && small_dist_end > 0; ) {
            // Add high-profit items with duplicate categories until we reach k items
            for (; big_dupl_beg < small_dist_end && used_count < k; ++big_dupl_beg) {
                if (!pos2used[big_dupl_beg]) {
                    pos2used[big_dupl_beg] = true;
                    ++used_count;
                    sum_profit += prof_cat[big_dupl_beg].first;
                }
            }
            res = max(res, sum_profit + distinct_count * distinct_count);

            // Try removing one lowest-profit distinct-category item
            // This frees up space to add another high-profit duplicate-category item
            for (--small_dist_end; small_dist_end > big_dupl_beg; --small_dist_end) {
                if (pos2used[small_dist_end]) {
                    pos2used[small_dist_end] = false;
                    --used_count;
                    sum_profit -= prof_cat[small_dist_end].first;
                    --distinct_count;
                    break;
                }
            }
        }

        return res;
    }
};

```
['C++']