Sort the array in the required order, and find out all the terms that have exactly the same data as the *k*-th one.

In fact, we can keep inserting *x* into the array until we find that the median is equal to *x*.

Why this works? One can see that if the median is less than *x*, then we should insert more integers that are larger than *x*; otherwise we should insert more integers that are less than *x*. Nevertheless, *x* can be viewed as an integer that is both “less than” and “larger than” *x* itself.

It can be proved that it is definitely sufficient to insert at most *n* + 1 *x*s, and thus the complexity is *N*^{2}*log*(*N*).

My codes have about 400 lines....

The basic idea is dp. We use *dp*[*i*][*j*] to denote the maximum profit we can obtain, when the *j*-th customer has made his decision (all the customers are sorted in an increasing order of their feet sizes *l*).

In details, *i* can take values 0, 1, 2, 3, which is in fact a bitmask. Note that when the *j*-th customer has feet size *l*[*j*] (we write *l* for short), he can buy shoes of size *s* = *l* and *s* = *l* + 1. We use 00 to denote that after the *j*-th customer has made his decision (he can buy one pair of shoes or nothing), shoes of size *s* = *l* and *s* = *l* + 1 are not sold, and use 01 to denote that after his decision, shoes of size *s* = *l* is not sold while that of size *s* = *l* + 1 is sold. Similarly, 10 denotes that after his decision, shoes of size *s* = *l* is sold while that of *s* = *l* + 1 is not sold. Finally, 11 denotes that both shoes of size *s* = *l* and *s* = *l* + 1 are sold.

Note that *dp*[*i*][*j*] only depends on *dp*[*i*][*j* - 1]. However, the recursicve formula should be deduced based on three cases.

1) *l*[*j*] = *l*[*j* - 1] + 1: for each state of *dp*[*i*][*j* - 1], i.e., 00, 01, 10, 11, the last bit denotes the shoes of the same size as that denoted by the first bit of states (also 00, 01, 10, 11) of *dp*[*i*][*j*]. This means that, for instance, 01 can not be transferred to states 00 and 01, since the shoes of size *l*[*j*] has been sold after the (*j* - 1)-th customer made his decision.

2) *l*[*j*] = *l*[*j* - 1]: the states of *dp*[*i*][*j* - 1] and *dp*[*i*][*j*] denote exactly the shoes of the same size. This means that, for instance, 01 can not be transferred to states 10 and 00 (similar reasons as above).

3) *l*[*j*] > *l*[*j* - 1] + 1: this means that the states of the *j*-th customer do not depend on those of *dp*[*i*][*j* - 1].

In case that the shoes of size *l* do not exist in the given input, we can still consider that this pair of shoes “exist” with zero cost.

We use *f*_{a}[*n*], *f*_{b}[*n*], *f*_{c}[*n*] and *f*_{d}[*n*] to denote the total number of ways to stay at nodes a, b, c and d after *n* steps, when we first start at node d. The recursive formula for each function is similar, and they all have forms of *f*_{a}[*n*] = *f*_{b}[*n* - 1] + *f*_{c}[*n* - 1] + *f*_{d}[*n* - 1]. Thus, we can adopt an array *dp*[4][*n*] to calculate and store all the results.

To further reduce the space complexity, note that *dp*[*i*][*n*] only depends on values of *dp*[*j*][*n* - 1], and thus it is sufficient to use *dp*[4][2] to store the values at the last step, and update values at the current step.