We'll pick a point P and count the number of non-empty sets where it is OUTSIDE the convex hull. Consider one such set. Since P is not contained in the hull, one can unambiguously choose another point Q which is the "most clockwise" of the points in the set. The rest of the set can then be any subset of the points within the 180° arc running counter-clockwise from Q.

A naive implementation would require cubic time, but by sorting all the points except P by the angle they make with P and then using a rotating line sweep, it can be reduced to $$$O(n \log n)$$$.

Because I want to compare subsets using c++ pair, I will define $$$w'_i=10^9-w_i$$$ so that if we put $$$(num,val)$$$ as a pair, we are taking the $$$K$$$ biggest ones.

The first observation you have to make is that you need to sort $$$d$$$. Then this is the claim. You can take a subset of items $$$i_1,i_2,\ldots,i_k$$$ if $$$d_{i_x} \leq i_x$$$ for all $$$x$$$. This is clearly necessary and it is also sufficient as we can assign item $$$i_x$$$ to be bought at time $$$x$$$.

From this, we can already solve a function $$$dp(i,j)$$$ that returns the maximal $$$(num,val)$$$ that we can make if we only consider after the $$$i$$$ items and we already took $$$j$$$ items.

Now, we will do a binary search over $$$(num,val)$$$. We want to check if there are less than $$$k$$$ subsets $$$(num',val')$$$ such that $$$(num',val')>(num,val)$$$.

We do a recursive function $$$search(i,j,num,val)$$$. Suppose that $$$dp(i,j)<(num,val)$$$, then we can return here, because we wont produce a child such that $$$(num',val')>(num,val)$$$. When we found $$$k$$$ children, we can return immediately. This way, we only use up to $$$O(n)$$$ time per child. Since we cut off our search after finding $$$k$$$ children, we only using $$$O(nk)$$$ time per search.

Combining this with binary search, we have a $$$O(nk \log)$$$ solution.

Code