九州大学プログラミングコンテスト2018 F - Team Making

解法

制約にbitDPをしてくださいと書いてあります。
ので、実際にbitDPを考えてみます。

$dp[S] =$ 今チームを組み終わっている人の状態が $S$ であるときの、これ以降のチームの組み方

とすると、まだチームを組めていない人の中で組めるようなチームの集合を $M$ として、
$\displaystyle dp[S] = \sum_{m \in M} dp[S+m]$
という遷移をしたくなりますが、これでは重複部分が存在してしまいます。
例えば、 $N = 2, K = 3000, A_{1} = A_{2} = 1000$
のようなパターンだと、上の遷移を行うことで、

先に1人目だけの1人のチームを組んでから、2人目だけのチームを作成
先に2人目だけの1人のチームを組んでから、1人目だけのチームを作成

というような、選ぶ順序を逆にしただけのものを区別することになります。
これを避けるために、まだ選んでいない人のうち、最も番号が若い人を確実に選ぶ、という制約を加えてあげると、うまく重複なく数え上げることができます。上の具体例では、前者だけがピックアップされます。
ということで、
$M$ を、改めて

$S$ に含まれていない人の中で、最も番号が若い人を必ず含むようなチームの組み方の集合

と定義しなおすことで、
$\displaystyle dp[S] = \sum_{m \in M} dp[S+m]$
という遷移でこの問題を解くことができるようになります。
1人チームは、その人のレートが $K$ を超えていようがいまいがチームを組めることに注意してください。
初期化は $dp[S_{all}] = 1$ で( $S_{all}$ は全ての人を含んだ状態)、答えは $dp[\varepsilon]$ ( $\varepsilon$ は空集合、すなわち誰も含まれていない状態)を見ればよいです。