2172. Maximum AND Sum of Array

You are given an integer array nums of length n and an integer numSlots such that 2 * numSlots >= n. There are numSlots slots numbered from 1 to numSlots.

You have to place all n integers into the slots such that each slot contains at most two numbers. The AND sum of a given placement is the sum of the bitwise AND of every number with its respective slot number.

• For example, the AND sum of placing the numbers [1, 3] into slot 1 and [4, 6] into slot 2 is equal to (1 AND 1) + (3 AND 1) + (4 AND 2) + (6 AND 2) = 1 + 1 + 0 + 2 = 4.

Return the maximum possible AND sum of nums given numSlots slots.

class Solution {
    unordered_map<string, int> dp;
    string makeKey(vector<int>& slots, int p) {
        stringstream key;

        key<<to_string(p);

        for(auto n : slots) {
            key<<to_string(n);
        }
        return key.str();
    }
    int solution(vector<int>& slots, vector<int>& remain, int p) {
        if(p == remain.size()) return 0;
        string key = makeKey(slots, p); 
        if(dp.count(key)) return dp[key];
        int res = 0;
        for(int i = 1; i < slots.size(); i++) {
            if(slots[i] == 2) continue;
            slots[i]++;
            res = max(res, solution(slots, remain, p + 1) + (i & remain[p]));
            slots[i]--;
        }
        return dp[key] = res;
    }
public:
    int maximumANDSum(vector<int>& nums, int numSlots) {
        unordered_map<int, int> m;
        vector<int> slots(numSlots + 1), remain;
        int res = 0, mi = 0;
        for(auto n : nums) m[n]++;
        for(int i = 1; i <= numSlots; i++) {
            slots[i] = min(2, m[i]);
            m[i] -= slots[i];
            mi += slots[i] * i;
            if(!m[i]) m.erase(i);
        }
        for(auto [k, v]:m) {
            while(v--) {
                remain.push_back(k);
            }
        }
        return mi + solution(slots, remain, 0);
    }
};