BRUTE works! C++ multiset (may use priority queue too!)


#1

vector Solution::solve(vector &A, vector &B, int C) {

int n = A.size();
multiset<int, greater<int>> st;

sort(A.begin(), A.end(), greater<int>());
sort(B.begin(), B.end(), greater<int>());

set<int>::iterator last;
vector<int> ans;

for(int i=0; i<n; i++)
{
    for(int j=0; j<n; j++)
    {
        if(st.size()<C)
        {
            st.insert(A[i]+B[j]);
            auto ed = st.end();
            ed--;
            last = ed;
        }
        else
        {
            if(*last < (A[i]+B[j]))
            {
                st.insert(A[i]+B[j]);
                last--;
            }
            else
            {
                break;
            }
        }
    }
}

for(int i=0; i<C; i++)
    ans.push_back(*(st.begin())),
    st.erase(st.begin());

return ans;

}