To begin with, let's observe a simple version of the task where the skyscraper heights are sorted ascendingly. Notice that then the heights don't have a role, it is sufficient to find the number of different subsets of skyscrapers such that the sum of the coins on them is larger than or equal to ~K~. A naive solution that tests every possibility is of complexity ~\mathcal O(2^N)~. We can halve the array of skyscrapers (let the first half contain ~N/2~ skyscrapers, and the other the rest). For the left half, we create a list ~L~ with all the sums of coins that can be obtained by testing all subsets of skyscrapers in the left half. For example, if the left half has ~3~ skyscrapers that contain on their roof, respectively, ~1~, ~2~ and ~3~ coins, when we will add the following values to list ~L~: ~(0, 1, 2, 3, 3, 4, 5, 6)~ - notice that the number ~3~ appears ~2~ times because there are ~2~ different ways which we can obtain that number of coins. Analogously, we will generate a list ~R~ for the right half. Now the task is broken down to the following: for each number in list ~L~, find how many numbers there are in list ~R~ such that their sum is less than or equal to ~K~. If we sort the numbers in the list ~R~, then the answer to that query can be found using binary search. Lists ~L~ and ~R~ consist of ~\mathcal O(2^{N/2})~ elements, so the total complexity of this algorithm is ~\mathcal O(N \times 2^{N/2})~.

The idea for solving the original task is similar. The only problem is the heights of the visited skyscrapers must be sorted ascendingly. For each valid subset of skyscrapers in the left half, we will add to list ~L~ the pair ~(s_L, h_L)~ where ~s_L~ denotes the sum of coins in the subset of skyscrapers, and ~h_L~ the height of the last skyscraper in the subset. For the right half, we will generate a similar list, the only difference being that we will add to list ~R~ the pair ~(s_R, h_R)~ where ~h_R~ represents the height of the first skyscraper in the subset. Now the task can be solved by counting, for each pair ~(s_L, h_L)~ from list ~L~, the number of pairs ~(s_R, h_R)~ in list ~R~ such that it holds ~s_L+s_R \ge K~ and ~h_R \ge h_L~. We can solve this by grouping the sums in list ~R~ by values ~h_R~, and for each pair ~(s_L, h_R)~ from the left half, we iterate over all groups for which ~h_R \ge h_L~, and determine the number of valid subsets by using binary search in the same way as it was explained for the simpler version.

This approach, where we divide the array into two parts and test every combination for each part, is known as meet-in-the-middle.