Hi guys. I was upsolving OI problems, when I stumbled upon this:

Statement: There are $$$n$$$ soldiers standing in a line, whose heights are distinct. A dude can be seen from the left side if there are no other dude to the left of him that is taller than him, and the same goes for the right side. Given $$$n$$$, $$$p$$$, $$$q$$$ ($$$n \leq 2000$$$), count how many way to arrange these dudes such that there are exactly $$$p$$$ dudes that can be seen from the left side, and $$$q$$$ dudes that can be seen from the right side. TL = $$$1$$$ second on a judge that runs as fast as Codeforces.

My idea: First we solve the case $$$q = 1$$$. For the sake of simplicity, we will assume the heights of these soldiers as a permutations of integers from $$$1$$$ to $$$n$$$. We can use dp: $$$f[i][j][k] = $$$ number of way to assign soldiers for the first $$$i$$$ position, such that the tallest soldiers that we assigned has the height $$$j$$$, and you can see $$$k$$$ dudes from the left side. From there it's just simple dp. For the general case, the answer is simply $$$\sum_{t = 1}^n (f[t-1][t-1][p-1] * f[n-t][n-t][q - 1] * C_{n-1} ^ {i-1})$$$. Sadly, this runs in $$$O(n^3)$$$, since our dp table has $$$n^3$$$ states.

I've discussed this problem with another dude who ranked Master on Codeforces, and we are proud to say that we can not cook, so any help would be appreciated. Thanks!