18o3 I know you were competing on leetcode a lot and they like such problems there but on codechef it's just meh

sorry :(

O(LB) was kind of cute to me. It isnt 18o3's fault.

greedily choose the island and check if they can be removed from the graph

Partition the set of vertices $$$V$$$ into two sets $$$A$$$ (in which vertex $$$1$$$ is present) and another set $$$B$$$. Now, if you want to disconnect vertex $$$1$$$ from all the vertices in set $$$B$$$, you shall not remove any edges which have both endpoints in either $$$A$$$ or $$$B$$$. So to disconnect them you would only remove edges between $$$A$$$ and $$$B$$$. Let the sum of $$$a[i]$$$ in set $$$B$$$ be $$$S$$$, and let the total sum of $$$a[i]$$$ be $$$T$$$. Then the cost is $$$(T - S) \times S$$$. For $$$S \leq \frac{T}{2}$$$, this formula achieves minima at small $$$S$$$, so you would one by one add smaller $$$a[i]$$$ to set $$$B$$$, until its $$$cost \le C.$$$ For $$$ S \gt \frac{T}{2} $$$, the minima is achieved when $$$S$$$ is as large as possible, so in such a case set $$$A$$$ contains the single vertex $$$1$$$. Check whether its $$$cost \leq C$$$, and then output the answer which has the minimum size of set $$$A$$$.

Its not monotonic actually

Let sumc be sum of Ais of chosen islands which will not be connected to 1 and sum be sum of all Ais

Then our cost is (sum-sum1)(sum1)<=c

There is an interval where sum1 is not allowed