2542. Maximum Subsequence Score

In this approach, we will try to maximize the sum by summing the maximum values together and multiplying the product with corresponding min values....

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) 
    {
        long long curr_sum=0;
        long long prod=0;
        long long ans=0;

        vector<pair<int,int>> vec;

        for(int i=0;i<nums1.size();i++)
        {
            vec.push_back({nums2[i],nums1[i]});
        }

        sort(vec.rbegin(),vec.rend());

        priority_queue<int,vector<int>,greater<int>> pq;

        for(int i=0;i<k-1;i++)
        {
            curr_sum+=vec[i].second;
            pq.push(vec[i].second);
        }

        for(int j=k-1;j<vec.size();j++)
        {
            curr_sum+=vec[j].second;
            pq.push(vec[j].second);

            prod=pq.top();
            ans=max(ans,curr_sum*vec[j].first);

            curr_sum-=prod;
            pq.pop();
        }

        return ans;

    }
};