P2159 [SHOI2009] Dance Party

# Description OItown is holding its annual super dance party. To make this year’s party bigger than ever, the organizer Constantine invited many of his friends and classmates. On the day of the party, exactly $n$ boys and $n$ girls came. Constantine noticed that, in general, in a pair the boy is taller than the girl, but there are occasional exceptions. So Constantine wants to know: if we pair these $2n$ people into exactly $n$ couples, how many ways are there such that at most $k$ couples have the girl taller than the boy? Now Constantine asks you, who is attending SHTSC, to compute the answer. Of course, he will first tell you the heights of all $2n$ students.

OItown 要举办一年一度的超级舞会了。 为了使今年的舞会规模空前，作为主办方的 Constantine 邀请了许多他的好友和同学去。 舞会那天，恰好来了 $n$ 个男生 $n$ 个女生。 Constantine 发现，一般情况下，舞伴之间，总是男伴总是比女伴长得高，不过，偶尔也是有特殊情况的。 所以，Constantine 现在想知道，如果把这 $2n$ 个人恰好配成 $n$ 对舞伴，有多少种搭配方法，使得最多只有 $k$ 对舞伴之间女伴比男伴高。 现在，Constantine 需要参加 SHTSC 的你帮助他算出这个答案。 当然啦，他会先告诉你这 $2n$ 个同学的身高。

第一行：两个整数 $n,k$，含义如问题中所示。 第 $2$ 行到第 $n+1$ 行：$n$ 个整数，表示 $n$ 个男生的身高。 第 $n+2$ 行到第 $2n+1$ 行：$n$ 个整数，表示 $n$ 个女生的身高。

Output a single integer in one line: the number of pairing schemes where among the $n$ couples, at most $k$ couples have the girl taller than the boy.

Constraints: For $100\%$ of the testdata, $1 \le n \le 200$, $0 \le k \le n$, and all heights are positive integers not greater than $10^9$. Translated by ChatGPT 5