<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code> of equal length <code>n</code> and a positive integer <code>k</code>. You must choose a <strong>subsequence</strong> of indices from <code>nums1</code> of length <code>k</code>.</p>

<p>For chosen indices <code>i<sub>0</sub></code>, <code>i<sub>1</sub></code>, ..., <code>i<sub>k - 1</sub></code>, your <strong>score</strong> is defined as:</p>

<ul>
	<li>The sum of the selected elements from <code>nums1</code> multiplied with the <strong>minimum</strong> of the selected elements from <code>nums2</code>.</li>
	<li>It can defined simply as: <code>(nums1[i<sub>0</sub>] + nums1[i<sub>1</sub>] +...+ nums1[i<sub>k - 1</sub>]) * min(nums2[i<sub>0</sub>] , nums2[i<sub>1</sub>], ... ,nums2[i<sub>k - 1</sub>])</code>.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> possible score.</em></p>

<p>A <strong>subsequence</strong> of indices of an array is a set that can be derived from the set <code>{0, 1, ..., n-1}</code> by deleting some or no elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
<strong>Output:</strong> 12
<strong>Explanation:</strong> 
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6. 
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12. 
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
<strong>Output:</strong> 30
<strong>Explanation:</strong> 
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums1.length == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums1[i], nums2[j] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>

class Solution {
public:
    void sort_w_folower(int *toSort, int *toFollow, int first, int last) {
        int l{first}, r{last}, m{(l + r) / 2}, pivot{0}, temp{0};
        // best way to choose pivot is to choose middle between left, middle and right.
        auto &left = toSort[l];
        auto &middle = toSort[m];
        auto &right = toSort[r];
        bool lm = left > middle;    
        bool mr = middle > right;
        bool rl = right > left;
        if ((lm && rl) || (!rl && !lm))        // m < l < r || r <= l <= m
            pivot = left;
        else if ((mr && lm) || (!lm && !mr))   // r < m < l ||  l <= m <= r
            pivot = middle;
        else //if ((rl && mr) || (!mr && !rl)) // l < r < m || m <= r <= l 
            pivot = right;
        
        do {
            while (toSort[l] > pivot) ++l;
            while (toSort[r] < pivot) --r;
            if (l <= r) {
                // swap left and right
                temp = toSort[l];
                toSort[l] = toSort[r];
                toSort[r] = temp;

                temp = toFollow[l];
                toFollow[l] = toFollow[r];
                toFollow[r] = temp;
                ++l;
                --r;
            }
        } while (l <= r);

        if (first < r) sort_w_folower(toSort, toFollow, first, r);
        if (l < last) sort_w_folower(toSort, toFollow, l, last);
    }

    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        const int size = nums1.size();
        int *d1 = nums1.data();
        int *d2 = nums2.data();

        int last{k};
        int64_t curSum{0}, maxScore{0};
        auto pairGreater = [](const pair<int, int> &p1, const pair<int, int> &p2) {
            return p1.first > p2.first;
        };
        priority_queue<pair<int, int>, 
                       vector<pair<int, int>>, 
                       decltype(pairGreater)> lpq;
        
        sort_w_folower(d1, d2, 0, size - 1);
        int pos{0};
        for (pos = 0; pos < k; ++pos) {
            curSum += d1[pos];
            lpq.push({d2[pos], pos});
        }
        
        while (true) {
            auto &[nums2, idx2] = lpq.top();
            maxScore = max(maxScore, curSum * d2[idx2]);

            if (pos == size)
                break;
            // remove idx2 from the heap and from the sum
            curSum -= d1[idx2];
            lpq.pop();
            // add next index to sum and to queue
            curSum += d1[pos];
            lpq.push({d2[pos], pos});
            ++pos;
        }
        return maxScore;
    }
};
89925